Long cycles in graphs with prescribed toughness and minimum degree (Q1894753): Difference between revisions

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.