Long cycles in graphs with prescribed toughness and minimum degree

Bauer, Douglas and Broersma, H.J. and Heuvel van den, J. and Veldman, H.J. (1995) Long cycles in graphs with prescribed toughness and minimum degree. Discrete Mathematics, 141 (1-3). pp. 1-10. ISSN 0012-365X

Preview

PDF
426Kb

Abstract:	A cycle C of a graph G is a Dλ-cycle if every component of G-V(C) has order less than λ. Using the notion of Dλ-cycles, a number of results are established concerning long cycles in graphs with prescribed toughness and minimum degree. Let G be a t-tough graph on n 3 vertices. If δ > n/(t + λ) + λ − 2 for some λ t + 1, then G contains a Dλ-cycle. In particular, if δ > n/(t + 1) − 1, then G is hamiltonian, improving a classical result of Dirac for t> 1. If G is nonhamiltonian and δ > n/(t + λ) + λ − 2 for some λ t + 1, then G contains a cycle of length at least (t + 1)(δ − λ + 2) + t, partially improving another classical result of Dirac for t> 1.
Item Type:	Article
Copyright:	© 1995 Elsevier
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/30081
Official URL:	http://dx.doi.org/10.1016/0012-365X(93)E0204-H
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page

Metis ID: 140720