Originator(s): Michael Ferrara, Angela Harris, Michael Jacobson, and Jenö Lehel (presented by Paul Wenger - REGS 2008)
Definitions: A graph G with n vertices is pancyclic if G contains cycles of lengths 3,4,...,n. The cycle spectrum of G is the set of the lengths of the cycles in G. The quantity σ2(G) is the smallest degree-sum of two nonadjacent vertices in G.
Background: Ore [O] proved that G is Hamiltonian if σ2≥n (unless G=K2). Bondy [B1] showed that in fact σ2≥n implies that G is pancyclic, unless G=Kn/2,n/2. Bondy's "Metaconjecture'' asserts that almost any nontrivial condition on a graph that guarantees a spanning cycle also implies that the graph is pancyclic, with possibly a small family of exceptional graphs.
Researchers have studied what is forced into the cycle spectrum by various conditions when the graph is separately required to have a spanning cycle. These results have led to results about Bondy's Metaconjecture, because they can be applied after some other condition forces a spanning cycle. For example, Schmeichel and Hakimi [SH] proved that if a spanning cycle in G has any two consecutive vertices x and y with degree-sum at least n, then G is pancyclic or bipartite or lacks only an (n-1)-cycle from the spectrum (if d(x)+d(y)≥n+1, then G is pancyclic). Bauer and Schmeichel [BS] used this to give unified proofs that the sufficient conditions of Chvátal [C], Fan [F], and Bondy [B2] for Hamiltonian cycles in fact imply pancyclicity, except for a small family of exceptions.
Ferrara, Harris and Jacobson [FHJ] continued this investigation. They showed that when two vertices separated by distance 2 along a spanning cycle have degree-sum at least n+1, again G is pancyclic. For vertex pairs with larger distance along a spanning cycle, the degree-sum threshold to force pancyclicity is larger. A bipartite analogue of the Schmeichel-Hakimi result exists: Schmeichel and Mitchem [SM] proved that in a bipartite graph, degree-sum at least n/2+1 for one pair of consecutive vertices on a spanning cycle forces all even cycle lengths, and degree-sum at least n/2+2 suffices when they have distance 2 along the cycle.
Now Jacobson and Lehel ask the opposite question: For weakenings of conditions that guarantee spanning cycles, how small can the spectrum be when the graph is known to be Hamiltonian? Graphs that are regular of degree n/2 are Hamiltonian and in fact pancyclic (except for Kn/2,n/2). Graphs that are 2-regular and Hamiltonian have only one cycle length, n. For degree greater than 2, the question becomes interesting.
Question: What is the minimum size of the cycle spectrum in a k-regular Hamiltonian graph, particularly for k=3?
Comments: By starting with n/6 copies of K3,3, cutting one edge from each, and linking the deficient vertices into a cycle that restores 3-regularity, it is easy to construct a 3-regular graph having only n/6+3 distinct cycle length. For k≤n/4, the construction generalizes to produce a k-regular graph with only [(n/2)(k-2)/k]+k distinct cycle lengths.
For the lower bound, it is relatively easy (by Ramsey's Theorem) to show that every 3-regular Hamiltonian graph has at least c log n cycle lengths. In REGS 2008, Milans and West showed that this lower bound can be increased to a multiple of n1/3, which is still a long way from the linear upper bound.
References:
[BS] Bauer, Douglas; Schmeichel, Edward;
Hamiltonian degree conditions which imply a graph is pancyclic.
J. Combin. Theory Ser. B 48 (1990), no. 1, 111--116.
[B1] Bondy, J.A.; Pancyclic Graphs.
J. Combin. Theory Ser. B 11 (1971), 80--84.
[B2] Bondy, J.A.; Longest paths and cycles in graphs of high degree,
Res. Rep. No. CORR 80-16, Univ. Waterloo, Waterloo, ON, 1980.
[C] Chvátal, V.; On Hamilton's ideals.
J. Combinatorial Theory Ser. B 12 (1972), 163--168.
[F] Fan, Genghua; New sufficient conditions for cycles in graphs.
J. Combin. Theory Ser. B 37 (1984), no. 3, 221--227.
[FHJ] Ferrara, Michael; Harris, Angela; Jacobson, Michael; Cycle lengths in
Hamiltonian graphs with a pair of vertices having large degree sum.
Preprint (2008).
[SH] Schmeichel, E. F.; Hakimi, S. L.;
A cycle structure theorem for Hamiltonian graphs.
J. Combin. Theory Ser. B 45 (1988), no. 1, 99--107.
[SM] Schmeichel, Edward; Mitchem, John;
Bipartite graphs with cycles of all even lengths.
J. Graph Theory 6 (1982), no. 4, 429--439.