Advanced Lower Bounds for the Circumference.

The classic lower bounds δ + 1 (Dirac), 2 δ (Dirac) and 3 δ − 3 (Voss and Zuluaga) for the circumference (the order of a longest cycle C in a graph G) are based on the minimum degree δ and some G\ C structures, combined with some additional connectivity conditions. A natural problem arises to find an analogous bound in a general form ( i + 1)( δ − i + 1) with i = 0, 1, . . . , δ, including the bounds δ + 1, 2 δ and 3 δ − 3 as special cases. In this paper we present two tight lower bounds for the circumference just of the form ( i + 1)( δ − i + 1) for each $${i\in\{0,\ldots,\delta\}}$$ based entirely on appropriate G\ C structures, actually escaping any other additional conditions: in each graph G, (i) $${|C|\geq(\overline{p}+1)(\delta-\overline{p}+1)}$$ and (ii) $${|C|\geq(\overline{c}+1)(\delta-\overline{c}+1),}$$ where $${\overline{p}}$$ and $${\overline{c}}$$ denote the orders of a longest path and a longest cycle in G\ C, respectively. [ABSTRACT FROM AUTHOR]