Cycles containing all vertices of maximum degree

Haitze J. Broersma, J.P.M. van den Heuvel, J. van den Heuvel, H.A. Jung, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
62 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 languageUndefined
Pages (from-to)373-385
Number of pages13
JournalJournal of graph theory
Volume17
Issue number17
DOIs
Publication statusPublished - 1993

Keywords

  • METIS-140367
  • IR-71002

Cite this

Broersma, H. J., van den Heuvel, J. P. M., van den Heuvel, J., Jung, H. A., & Veldman, H. J. (1993). Cycles containing all vertices of maximum degree. Journal of graph theory, 17(17), 373-385. https://doi.org/10.1002/jgt.3190170311