r-regular graphs are not uniquely hamiltonian.

Importance: High ✭✭✭
Author(s): Sheehan, John
Recomm. for undergrads: no
Posted by: Robert Samal
on: July 24th, 2007

\begin{conjecture} If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian. \end{conjecture}

(Reproduced from [M].)

A graph $G$ is said to be \emph{uniquely hamiltonian} if it contains precisely one \Def[Hamiltonian cycle]{hamiltonian cycle}.

This conjecture has been proved for all odd values of $r$ [T] and for all even values of $r > 23$ [H]. By Petersen's theorem, it would suffice to prove it for $r = 4$.


[H] P. Haxell, Oberwolfach reports, 2006.

[M] Bojan Mohar, \href[Problem of the Month]{http://www.fmf.uni-lj.si/~mohar/Problems/P0703_HamiltonicityInfinite.html}

*[S] John Sheehan: The multiplicity of Hamiltonian circuits in a graph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 477-480. Academia, Prague, 1975, \MRhref{MR0398896}

[T] A.G. Thomason, 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.

* indicates original appearance(s) of problem.