A generalization of Bondy’s pancyclicity theorem

The bipartite independence number of a graph G , denoted as α (G) , is the minimal number k such that there exist positive integers a and b with $a+b=k+1$ with the property that for any two disjoint sets A,B⊆ V(G) with $|A|=a$ and $|B|=b$ , there is an edge between A and B . McDiarmid and Yolov showed that if δ (G)≥ α (G) then G is Hamiltonian, extending the famous theorem of Dirac which states that if δ (G)≥ |G|/2 then G is Hamiltonian. In 1973, Bondy showed that, unless G is a complete bipartite graph, Dirac’s Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from $3$ up to n . In this paper, we show that δ (G)≥ α (G) implies that G is pancyclic or that G=Kn/2,n/2 , thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.