Document Type
Lecture
Publication Date
3-27-2024
Abstract
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 Gis 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 σ2(G) = 2n t+1 − 2 but G is non-hamiltonian. This is joint work with Masahiro Sanka.
Relational Format
presentation
Recommended Citation
Shan, Songling, "An Ore-type condition for hamiltonicity in tough graphs and the extremal examples" (2024). Combinatorics Seminar. 10.
https://egrove.olemiss.edu/math_combinatorics/10
