2022/10/31 by Sanka, Masahiro, Shan, Songling · 1 citation
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.2210.17006
openalex publication_date 2022/10/31 · openalex created_date 2022/11/06 · openalex updated_date 2026/07/28
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 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 σ2(G) = (2n)/(t+1)-2 but G is non-hamiltonian.