Cycles containing all vertices of maximum degree

H.J. Broersma, J. van den Heuvel, H.A. Jung, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
68 Downloads (Pure)

Abstract

For a graph G and an integer k, denote by Vk the set {v ε V(G) | d(v) ≥ k}. 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.
Original languageEnglish
Pages (from-to)373-385
Number of pages13
JournalJournal of graph theory
Volume17
Issue number3
DOIs
Publication statusPublished - 1993

Fingerprint Dive into the research topics of 'Cycles containing all vertices of maximum degree'. Together they form a unique fingerprint.

Cite this