Cycles containing all vertices of maximum degree

Share/Save/Bookmark

Broersma, H.J. and Heuvel, J. van den 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

open access
[img]
Preview
PDF
536kB
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.
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