An Ore-Type Condition for Hamiltonicity in Tough Graphs and the Extremal Examples

Let G be a t-tough graph on n≥ 3 vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of G is greater than n/t+1-1, then G is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when t is between 1 and 2, and recently the second author proved a general result. The result states that if the degree sum of any two nonadjacent vertices of G is greater than 2n/t+1+t-2, then G is hamiltonian. It was conjectured in the same paper that the "$+t$" in the bound 2n/t+1+t-2 can be removed. Here we confirm the conjecture. The result generalizes the result by Bauer, Broersma, van den Heuvel, and Veldman. Furthermore, we characterize all t-tough graphs G on n≥ 3 vertices for which σ₂(G) = 2n/t+1-2 but G is non-hamiltonian.