Conjectures on Pancyclic Graphs

Hao Li
Centre National de la Recherche Scientifique
and University of Memphis

A graph of order n is said to be pancyclic if it contains cycles of all lengths from 3 to n. Bondy suggested the interesting "metaconjecture" that almost any nontrivial condition on graphs which implies that the graph is hamiltonian also implies that the graph is pancyclic (there may be a family of exceptional graphs). This "metaconjecture" has been verified for many important conditions, for example Ore's condition, Chvatal's condition, Fan's condition and Bondy's condition etc. Another important result due to Chvatal and Erdos states that every k-connected graph on at least 3 vertices with stability alpha at most k is hamiltonian. We obtain results on pancyclic related to Chvatal and Erdos' condition.