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.
| Original language | English |
|---|---|
| Pages (from-to) | 1-10 |
| Number of pages | 11 |
| Journal | Discrete mathematics |
| Volume | 141 |
| Issue number | 141 |
| DOIs | |
| Publication status | Published - 1995 |
Keywords
- METIS-140720
- IR-30081
Fingerprint
Dive into the research topics of 'Long cycles in graphs with prescribed toughness and minimum degree'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver