Degree sequence condition for pancyclicity in tough graphs

Abstract

Let $t\ge 1$ be an integer, and let $G$ be a $t$-tough $n$-vertex graph with degree sequence $d_1,d_2,\dots ,d_n$ in non-decreasing order. In 1995, Hoàng conjectured that if $G$ is Hamiltonian and, for every integer $i$ satisfying $t\le i<n/2$, $d_i\le i$, and $d_{n-i+t}<n-i$, one has $d_j+d_{n-j+t}\ge n$ for all $j$ with $i<j<\frac{n}{2}$, then $G$ is pancyclic or bipartite. In this paper, we disprove the conjecture for $t=1$ and confirm it for all $t\ge 7$.