Long cycles in graphs with prescribed toughness and minimum degree

Douglas Bauer, Haitze J. Broersma, J.P.M. van den Heuvel, J. van den Heuvel, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)
71 Downloads (Pure)

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 languageEnglish
Pages (from-to)1-10
Number of pages11
JournalDiscrete mathematics
Volume141
Issue number141
DOIs
Publication statusPublished - 1995

    Fingerprint

Keywords

  • METIS-140720
  • IR-30081

Cite this

Bauer, D., Broersma, H. J., van den Heuvel, J. P. M., van den Heuvel, J., & Veldman, H. J. (1995). Long cycles in graphs with prescribed toughness and minimum degree. Discrete mathematics, 141(141), 1-10. https://doi.org/10.1016/0012-365X(93)E0204-H