Princeton Discrete Math Seminar


Weakly Pancyclic Graphs


Bela Bollobas
IAS, Memphis and Cambridge


Fine Hall 224
Princeton University


2:30 - 3:30 pm
Wednesday, December 4, 1996

In the talk we shall present some recent results, obtained jointly with Andrew Thomason. A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. A substantial result of Haggkvist, Faudree and Schelp (1981) states that a Hamiltonian non-bipartite graph of order n and size at least

[(n-1)^2/4] + 2

contains cycles of every length between 3 and n. From this, Brandt (1996) deduced that every non-bipartite graph of the stated order and size is weakly pancyclic. He conjectured the much stronger assertion that it suffices to demand that the size be at least

n^2/4 - n + 5.

One of our main results is a slightly weaker form of this conjecture, namely that every graph of order n and size at least

[n^2/4] - n + 59

is weakly pancyclic or bipartite.

Document last modified on December 3, 1996