ON THE GIRTH OF HAMILTONIAN WEAKLY PANCYCLIC GRAPHS

A graph is called weakly pancyclic if it contains cycles of all length s between its girth and circumference. In answer to a question of Erdo s, we show that a Hamiltonian weakly-pancyclic graph of order n can ha ve girth as large as about 2 root n/logn. In contrast to this, we show that the existence of a cycle of length at most 2 root n - 1 is alrea dy implied by the existence of just two long cycles, of lengths n and n -1. Moreover we show that any graph, Hamiltonian or otherwise, which has n - c edges will have girth of order at most (n/c) log c, (C) 199 7 John Wiley & Sons, Inc.