Pancyclicity of Hamiltonian and highly connected graphs

Abstract

A graph G on n vertices is Hamiltonian if it contains a cycle of length n and pancyclic if it contains cycles of length $\ell$ for all $3\le \ell \le n$. Write $\alpha (G)$ for the independence number of $G$, i.e. the size of the largest subset of the vertex set that does not contain an edge, and $\kappa (G)$ for the (vertex) connectivity, i.e. the size of the smallest subset of the vertex set that can be deleted to obtain a disconnected graph. A celebrated theorem of Chvátal and Erdős says that $G$ is Hamiltonian if $\kappa (G)\ge \alpha (G)$. Moreover, Bondy suggested that almost any non-trivial conditions for Hamiltonicity of a graph should also imply pancyclicity. Motivated by this, we prove that if $\kappa (G)\ge 600\alpha (G)$ then G is pancyclic. This establishes a conjecture of Jackson and Ordaz up to a constant factor. Moreover, we obtain the more general result that if G is Hamiltonian with minimum degree $\delta (G)\ge 600\alpha (G)$ then G is pancyclic. Improving an old result of Erdős, we also show that G is pancyclic if it is Hamiltonian and $n\ge 150\alpha (G{)}^3$. Our arguments use the following theorem of independent interest on cycle lengths in graphs: if $\delta (G)\ge 300\alpha (G)$ then G contains a cycle of length $\ell$ for all $3\le \ell \le \delta (G)/81$.

15 pages, 1 figure