Weakly pancyclic graphs

Abstract

In generalizing the concept of a pancyclic graph, we say that a graph is “weakly pancyclic” if it contains cycles of every length between the length of a shortest and a longest cycle. In this paper it is shown that in many cases the requirements on a graph which ensure that it is weakly pancyclic are considerably weaker than those required to ensure that it is pancyclic. This sheds some light on the content of a famous metaconjecture of Bondy. From the main result of this paper it follows that 2-connected nonbipartite graphs of sufficiently large order n with minimum degree exceeding 2n/7 are weakly pancyclic; and that graphs with minimum degree at least n/4 + 250 are pancyclic, if they contain both a triangle and a hamiltonian cycle. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 141–176, 1998