Long cycles in graphs with prescribed toughness and minimum degree

Share/Save/Bookmark

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

[img]
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:
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