Weakly pancyclic graphs

A graph is called weakly pancyclic ii it contains cycles of all lengths bet ween its girth and circumference. A substantial result of Haggkvist, Faudre e, and Schelp (1981) states that a Hamiltonian non-bipartite graph of order ii and size at least [(n-1)(2)/4] + 2 contains cycles of every length l, 3 less than or equal to l less than or equal to n. From this, Brandt (1997) deduced that every non-bipartite graph of the stated order and size is weak ly pancyclic. He conjectured the much stronger assertion that it suffices t o demand that the size be at least [n(2)/4]-n + 5. We almost prove this con jecture by establishing that every graph of order n and size at least [n(2) /4]- n + 59 is weakly pancyclic or bipartite. (C) 1999 Academic Press.