Activities per year
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 language | English |
---|---|
Pages (from-to) | 373-385 |
Number of pages | 13 |
Journal | Journal of graph theory |
Volume | 17 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1993 |
Fingerprint
Dive into the research topics of 'Cycles containing all vertices of maximum degree'. Together they form a unique fingerprint.Activities
- 1 Oral presentation
-
Cycles containing all vertices of maximum degree
Veldman, H. J. (Speaker)
9 Apr 1992Activity: Talk or presentation › Oral presentation