11
$\begingroup$

A graph is uniquely hamiltonian if it has exactly one Hamilton cycle.

As every edge in a cubic graph lies in an even number of Hamilton cycles, a cubic graph cannot be uniquely hamiltonian, and a famous conjecture, called Sheehan's conjecture asserts that a 4-regular graph can also not be uniquely hamiltonian.

Apparently, however, there are uniquely hamiltonian graphs with minimum degree equal to four - the latest edition of Bondy & Murty's Graph Theory even gives a reference to a paper by H. Fleischner entitled "Uniquely hamiltonian graphs of minimum degree 4", To Appear, Journal of Graph Theory and dates it at 2007.

But I cannot find this paper on MathSciNet and nor can I find any paper that appears to contains these graphs. Googling reveals a few references to this work, including a 2003 conference/workshop where the abstract claims that there are some uniquely hamiltonian Eulerian graphs with minimum degree four.

Does anyone know what these graphs are? Or where this paper is? Or anything at all?

(I have emailed Fleischner but had no reply yet, though I may still get one as the email was recent.)

EDIT: Due to some bizarre synchronicity, I received a reply from Herbert Fleischner literally 5 seconds after I finished writing this question; the paper exists and has been accepted by JGT but final revisions have not been made.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Here is the abstract of a talk that Herbert Fleischner gave at CombinaTexas: Combinatorics in the South-Central U.S., available at this link, in 2003. The title of his talk was, "Uniquely Hamiltonian Graphs":

Abstract: In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs having precisely one Hamiltonian cycle (= uniquely Hamiltonian graphs). In the early 1990s, 4-regular loopless uniquely Hamiltonian multigraphs were constructed whose underlying uniquely Hamiltonian (simple) graphs have 3- and 4-valent vertices only. C.Thomassen showed that regular graphs of sufficiently high degree cannot be uniquely Hamiltonian; and J.A.Bondy, in his article for the Handbook of Combinatorics, asked whether uniquely Hamiltonian graphs must have a vertex of degree 2 or 3. Starting from the examples quoted above, one can construct Eulerian uniquely Hamiltonian graphs of minimum degree 4.

See also The Open Problems Garden, "Uniquely Hamiltonian graphs," which highlights the conjecture:

If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely Hamiltonian.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah yes, this abstract is the one that I encountered on my initial search, but could not recall where it came from. However it still doesn't give more than a vague hint about the graphs themselves. I hope that all will be revealed when Herb Fleischner sends me the revised paper (as his email said he would) as I would like to see why these graphs "work". I was, and remain, intrigued by the idea that the existence of a 2nd hamiltonian cycle is forced by regularity, but not simply by the presence of "enough edges". $\endgroup$
    – Gordon Royle
    Commented Feb 5, 2012 at 9:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .