Long Cycles in 1-tough Graphs

Original · EN

In 1952, Dirac proved that every 2-connected graph with minimum degree δ either is hamiltonian or contains a cycle of length at least 2δ. In 1986, Bauer and Schmeichel enlarged the bound 2δ to 2δ+2 under additional 1-tough condition - an alternative and more natural necessary condition for a graph to be hamiltonian. In fact, the bound 2δ+2 is sharp for a graph on n vertices when n≡ 1(mod3). In this paper we present the final version of this result which is sharp for each n: every 1-tough graph either is hamiltonian or contains a cycle of length at least 2δ+2 when n≡ 1(mod3), at least 2δ+3 when n≡ 2(mod3) or n≡ 1(mod4), and at least 2δ+4 otherwise.