# Princeton Discrete Math Seminar

## Title:

Weakly Pancyclic Graphs

## Speaker:

- Bela Bollobas
- IAS, Memphis and Cambridge

## Place:

- Fine Hall 224
- Princeton University

## Time:

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

Abstract:
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