15
$\begingroup$

I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one.

(Recall that a graph is hamiltonian if it has a cycle passing through each vertex exactly once, and is uniquely hamiltonian if there is only one such cycle.)

Here's the smallest one that I currently know.

enter image description here

Does anyone know if a smaller one (fewer vertices) has been published?

Improve this question
$\endgroup$
9
  • $\begingroup$ What are the numbers placed for? They definitely don't indicate the cycle (which is obvious). Do they bear some additional info? $\endgroup$ – Ilya Bogdanov Nov 28 '16 at 9:18
  • $\begingroup$ The numbers are just an arbitrary labelling so no further information there. $\endgroup$ – Gordon Royle Nov 28 '16 at 9:24
  • 2
    $\begingroup$ A google search brings up this article: link.springer.com/chapter/10.1007%2F978-3-319-39636-1_1. And it claims there is such a graph on only 10 vertices. $\endgroup$ – Wolfgang Nov 28 '16 at 11:10
  • $\begingroup$ @Wolfgang This is a very strange paper. I agree that it claims that there is such a graph on 10 vertices. However it does not actually contain any graphs, except for a diagram (Figure 1) of a 10-vertex graph that is not uniquely hamiltonian. The paper spends almost all its time on an extended description of a search algorithm that judging by the number of acronyms used must be quite complicated, and plenty of tables of running times and success rates etc. But no uniquely hamiltonian graphs :-( $\endgroup$ – Gordon Royle Nov 28 '16 at 12:05
  • $\begingroup$ Aha, figured it out. The 10-vertex graph in the aforementioned paper has the property that it has an edge that is contained in only one hamilton cycle. This means it can be turned into a uniquely hamiltonian graph via a simple doubling procedure. So while the 10-vertex graph itself is not uniquely hamiltonian, it leads to a 20-vertex example that is. $\endgroup$ – Gordon Royle Nov 28 '16 at 12:34
9
$\begingroup$

I am not sure what the smallest such graph is, but since you also asked for more information on uniquely hamiltonian graphs with minimum degree $3$, Entringer and Swart proved the following nice theorem.

For each $n= 2k, k \geqslant 11$, there exists a uniquely hamiltonian graph on $n$ vertices having two vertices of degree $4$ and all others of degree $3$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, I came across this paper, and wondered whether their 22-vertex example might be the smallest, which really started me off on trying to find the smallest. My guess is that my 18-vertex example is the smallest, but I haven't confirmed this yet. I do know that it is the only one with this number of vertices and edges. $\endgroup$ – Gordon Royle Nov 28 '16 at 10:14
9
$\begingroup$

The system encouraged me to answer my own question, although it feels a bit strange to do so.

Anyway, after a bit of thinking and a (more substantial) bit of computing, I can now safely conclude that this 18-vertex 28-edge graph is the smallest uniquely-hamiltonian graph with minimum degree 3, and there are no others of this order (number of vertices) and size (number of edges).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.