Chvátal-Erdo ̋s condition for pancyclicity

Abstract

An n-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from 3 up to n. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph G withκ(G)>(1+o(1))α(G)ispancyclic.ThisextendsthefamousChvátal-Erdo ̋scondition for Hamiltonicity and proves asymptotically a 30-year old conjecture of Jackson and Ordaz.