TY - JOUR

T1 - Long cycles in graphs with prescribed toughness and minimum degree

AU - Bauer, Douglas

AU - Broersma, Haitze J.

AU - van den Heuvel, J.P.M.

AU - van den Heuvel, J.

AU - Veldman, H.J.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

KW - METIS-140720

KW - IR-30081

U2 - 10.1016/0012-365X(93)E0204-H

DO - 10.1016/0012-365X(93)E0204-H

M3 - Article

VL - 141

SP - 1

EP - 10

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 141

ER -