A strengthening of a degree sequence condition for Hamiltonicity in tough graphs

Abstract

Generalizing Chvátal's classic 1972 result, Hoàng proposed in 1995 the following conjecture, which strengthens Chvátal's result in terms of toughness: Let $t\ge 1$ be a positive integer and $G$ be a $t$-tough graph on $n\ge 3$ vertices with degree sequence $d_1,d_2,\dots ,d_n$ in non-increasing order. Suppose for each $i\in [1,\lfloor \frac{n-1}{2}\rfloor ]$, if $d_i\le i\text{ and }{d}_{n-i+t}<n-i$ implies $d_j+d_{n-j+t}\ge n$ for all $j\in [i+1,\lfloor \frac{n-1}{2}\rfloor ]$, then $G$ is Hamiltonian. Hoàng verified the conjecture for $t=1$. In this paper, we verfity the conjecture for all $t\ge 4$. Our proof relies on a toughness closure lemma for $t\ge 4$ that we previously established. Additionally, we show that the toughness closure lemma does not hold when $t=1$.