On the structure of the set of cycle lengths in a hamiltonian graph Original Research Article

We study the set of cycle lengths in a hamiltonian graph G of order n with two fixed and nonadjacent vertices x, y whose degree sum satisfies d(x)+d(y)⩾n+z, where z⩾1. We prove that this set contains all integers between 3 and 4n+4z+3219. This improves and generalizes some results of Faudree et al. (Discuss. Math. Graph Theory 16 (1996) 27) and Schelten and Schiermeyer (Discrete Appl. Math. 79 (1997) 201). We also show that if z⩾518n then G contains a cycle of length p for every p satisfying 3⩽p⩽n2+z2+1.