Cycles in hamiltonian graphs of prescribed maximum degree Original Research Article

Let G be a hamiltonian graph G of order n and maximum degree Δ, and let C(G) denote the set of cycle lengths occurring in G. It is easy to see that |C(G)|⩾Δ−1. In this paper, we prove that if Δ>n/2, then |C(G)|⩾(n+Δ−3)/2. We also show that for every Δ⩾2 there is a graph G of order n⩾2Δ such that |C(G)|=Δ−1, and the lower bound in case Δ>n/2 is best possible.