On the girth of hamiltonian weakly pancyclic graphs

Abstract

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. In answer to a question of Erdös, we show that a Hamiltonian weakly-pancyclic graph of order n can have girth as large as about . In contrast to this, we show that the existence of a cycle of length at most - 1 is already 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. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 165–173, 1997