Originators: Sheehan, Haxell-Seamone-Verstraete (presented by Douglas West- REGS 2007)
Conjecture 1 (Sheehan, 1975): Every 4-regular Hamiltonian graph has at least two Hamiltonian cycles.
Background: Cedric Smith (see [Tu]) proved that every edge in a 3-regular graph appears in an even number of Hamiltonian cycles. Andrew Thomason [Ta] gave an elegant short proof of this using the fact that every graph has an even number of vertices of odd degree; he applied this to his auxiliary "lollipop" graph defined on the Hamiltonian paths starting from a fixed vertex through a fixed edge. His result stengthens Smith's Theorem by giving the same conclusion whenever all vertex degrees are odd.
Carsten Thomassen [Tc1] showed that the argument of [Ta] also guarantees an extra Hamiltonian cycle when for some Hamiltonian cycle C there is a C-independent dominating set (C-ID set); this is a set A of vertices such that A has no two consecutive vertices on C and every vertex outside A has a neighbor in A via an edge not in C. In [Tc2], he used this notion to show that when r>72, every r-regular Hamiltonian graph has at least two Hamiltonian cycles.
Thomassen's result can be viewed as evidence in support of Sheehan's Conjecture. The threshold was extended to r>48 by Ghandehari and Hatami [GH] and to r>22 by Haxell, Seamone, and Verstraete [HSV]. They find a C-ID set using the Lovász Local Lemma and ask two additional questions.
Question 1: Is it true that for every spanning cycle C in a 5-regular graph there is a C-ID set? (The answer is "no" for 4-regular graphs.)
Question 2: Given a spanning cycle in a 3-regular graph, is there a polynomial algorithm to produce another spanning cycle?
References:
[GH] M. Ghandehari and H. Hatami, A note on independent dominating sets and
second hamiltonian cycles (unpublished).
[HSV] Haxell, Penny; Seamone, Ben; Verstraete, Jacques;
Independent dominating sets and Hamiltonian cycles.
J. Graph Theory 54 (2007), no. 3, 233--244.
[S] Sheehan, John. The multiplicity of Hamiltonian circuits in a graph.
Recent advances in graph theory (Proc. 2nd Czechoslovak Sympos., Prague,
1974), pp. 477--480. Academia, Prague, 1975.
[Ta] Thomason, A. G. Hamiltonian cycles and uniquely edge colourable graphs.
Advances in graph theory (Cambridge Combinatorial Conf., Trinity College,
Cambridge, 1977). Ann. Discrete Math. 3 (1978), Exp. No. 13, 3 pp.
[Tc1] Thomassen, Carsten. Chords of longest cycles in cubic graphs.
J. Combin. Theory Ser. B 71 (1997), no. 2, 211--214.
[Tc2] Thomassen, Carsten. Independent dominating sets and a second Hamiltonian
cycle in regular graphs. J. Combin. Theory Ser. B 72 (1998), no. 1, 104--109.
[Tu] Tutte, W. T. On Hamiltonian circuits.
J. London Math. Soc. 21, (1946). 98--101.