Long cycles in graphs with prescribed toughness and minimum degree (Q1894753)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long cycles in graphs with prescribed toughness and minimum degree |
scientific article |
Statements
Long cycles in graphs with prescribed toughness and minimum degree (English)
0 references
24 July 1995
0 references
The authors improve upon two classical results of Dirac which relate the hamiltonicity of a graph or the length of a longest cycle in a nonhamiltonian graph to its minimum degree \(\delta\). The improvement is done by considering the toughness of the graph and by employing the notion of a \(D_\lambda\)-cycle. A cycle \(C\) in a graph \(G\) is a \(D_\lambda\)-cycle if each component of \(G - V(C)\) has less than \(\lambda\) vertices. If \(G\) is a \(t\)-tough graph on \(n \geq 3\) vertices, the following are true: If \(\delta > n/(t + \lambda) + \lambda - 2\) for some \(\lambda \leq t + 1\), then \(G\) contains a \(D_\lambda\)-cycle. For \(t = 1\) this means \(G\) is hamiltonian. If \(G\) is nonhamiltonian, then the same condition on \(\delta\) ensures a longest cycle of length at least \((t + 1) (\delta - \lambda + 2) + t\). The authors obtain a variety of other analogues to Dirac's theorems.
0 references
circumference
0 references
hamiltonicity
0 references
longest cycle
0 references
minimum degree
0 references
toughness
0 references
cycle
0 references