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 − 3 2 } , which if G is bipartite implies that s ( G ) ≥ min { ⌊ 4 ( m − 1 ) n − 2 ⌋ , n − 2 2 } , where m is the number of edges in G .