Long cycles in graphs with prescribed toughness and minimum degree

✍ Scribed by Douglas Bauer; H.J. Broersma; J. van den Heuvel; H.J. Veldman

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 427 KB
• Volume: 141
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0204-h

✦ Synopsis

A cycle C of a graph G is a D~-cycle if every component of G-V(C) has order less than 2. 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 6 > n/(t + 2) + 2-2 for some 2 ~< t + 1, then G contains a Dx-cycle. In particular, if 6>n/(t+ 1)--1, then G is hamiltonian, improving a classical result of Dirac for t> 1. If G is nonhamiltonian and 6 > n/(t + 2) + 2-2 for some 2 ~< t + 1, then G contains a cycle of length at least (t +1)(6-,~ + 2)+ t, partially improving another classical result of Dirac for t> 1.