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

Preview

PDF
524Kb

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140367