Pancyclicity of highly connected graphs

Abstract

A well-known result due to Chvatál and Erdős (1972) asserts that, if a graph $G$ satisfies $\hat{I}º(G)\ge \hat{I}\pm (G)$, where $\hat{I}º(G)$ is the vertex-connectivity of $G$, then $G$ has a Hamilton cycle. We prove a similar result implying that a graph $G$ is pancyclic, namely it contains cycles of all lengths between $3$ and $|G|$: if $|G|$ is large and $\hat{I}º(G)>\hat{I}\pm (G)$, then $G$ is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Draganić, Munhá-Correia, and Sudakov.

30 pages, 11 figures, made some minor changes following referee's comments