Home » Subject » Graph Theory » Basic G.T. » Cycles
Importance: High ✭✭✭
Author(s): Sheehan, John
Subject: Graph Theory
» Basic Graph Theory
» » Cycles
Keywords: hamiltonian
regular
uniquely hamiltonian
Recomm. for undergrads: no
Posted by: Robert Samal
on: July 24th, 2007
Conjecture   If $ G $ is a finite $ r $-regular graph, where $ r > 2 $, then $ G $ is not uniquely hamiltonian.

(Reproduced from [M].)

A graph $ G $ is said to be uniquely hamiltonian if it contains precisely one 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 $.

Bibliography

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

[M] Bojan Mohar, Problem of the Month

*[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, MathSciNet

[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.
3 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options