2024/05/08 by Shan, Songling, Tanyel, Arthur · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.04728
Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvátal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a graph. Hoàng in 1995 generalized Chvátal's degree sequence condition for 1-tough graphs and conjectured a t-tough analogue for any positive integer t≥ 1. Hoàng in the same paper verified his conjecture for t≤ 3 and recently Hoàng and Robin verified the conjecture for t=4. In this paper, we confirm the conjecture for all t≥ 4. The proof depends on two newly established results on cycle structures in tough graphs, which hold independent interest.