A generalization of Bondy’s pancyclicity theorem

Abstract 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=K₍₂, n{2}, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.