A Sharp Improvement of a Theorem of Bauer and Schmeichel - Nikoghosyan, Zhora G. (Mathematical Problems of Computer Science, 2021)
Let G be a graph on n vertices with minimum degree δ. The earliest nontrivial lower bound for the circumference c (the length of a longest cycle in G) was established in 1952 due to Dirac in terms of n and δ: (i) if G is a 2-connected graph, then c ≥ minn, 2δ. The bound in Theorem (i) is sharp. In 1986, Bauer and Schmeichel gave a version of this classical result for 1-tough graphs: (ii) if G is a 1-tough graph, then c ≥ minn, 2δ + 2. In this paper we present an improvement of (ii), which is sharp for each n: (iii) if G is a 1-tough graph, then c ≥ minn, 2δ + 2 when n ≡ 1(mod 3); c ≥ minn, 2δ + 3 when n ≡ 2(mod 3) or n ≡ 1(mod 4); and c ≥ minn, 2δ + 4 otherwise.