Estimates on the size of the cycle spectra of Hamiltonian graphs

Given a graph G, let S(G) be the set of all cycle lengths contained in G and let s(G)=|S(G)|. Let ℒ(G)={3,…,n}∖S(G) and let d be the greatest common divisor of n−2 and all the positive pairwise differences of elements in ℒ(G). We prove that if a Hamiltonian graph G of order n has at least n(p+2)4+1 edges, where p is an integer such that 1≤p≤n−2, then s(G)≥p or G is exceptional, by which we mean d∤(ℓ−2) for some ℓ∈ℒ(G). We also discuss cases where G is not exceptional, for example when n−2 is prime. Moreover, we show that s(G)≥min{p,n−32}, which if G is bipartite implies that s(G)≥min{⌊4(m−1)n−2⌋,n−22}, where m is the number of edges in G.