# Cycles containing all vertices of maximum degree

Broersma, H.J. and Heuvel van den, J. and Jung, H.A. and Veldman, H.J. (1993) *Cycles containing all vertices of maximum degree.* Journal of Graph Theory, 17 (3). pp. 373-385. ISSN 0364-9024

| PDF 524Kb |

Abstract: | For a graph G and an integer k, denote by Vk the set . Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. |

Item Type: | Article |

Copyright: | © 1993 Wiley InterScience |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/71002 |

Official URL: | http://dx.doi.org/10.1002/jgt.3190170311 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 140367