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?

Added years later (2023)

With almost any extremal question in Hamiltonicity the Petersen graph crops up and this is no exception.

This picture shows that the graph can be partitioned into two 9-vertex induced subgraphs, each obtained by deleting a vertex from the Petersen graph and then joined by four judiciously chosen edges.

The graph can be shown to be uniquely Hamiltonian by arguing in the "half-graph" about how paths can connect the four "terminals" (vertices with edges to the other side).

Minimal UH3 Graph

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
    Commented Nov 28, 2016 at 9:18
  • $\begingroup$ The numbers are just an arbitrary labelling so no further information there. $\endgroup$
    – Gordon Royle
    Commented Nov 28, 2016 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
    Commented Nov 28, 2016 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
    Commented Nov 28, 2016 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
    Commented Nov 28, 2016 at 12:34

2 Answers 2

Reset to default
10
$\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$
2
  • $\begingroup$ Is there any description of this graph other than giving a list of its edges? $\endgroup$
    – Fedor Petrov
    Commented Dec 24, 2023 at 18:49
  • $\begingroup$ @FedorPetrov Yes, there is a nice description - two copies of $P-v$ connected together appropriately, where $P$ is the Petersen graph. I can't draw pictures in comments so I've added the diagram to the question. $\endgroup$
    – Gordon Royle
    Commented Dec 26, 2023 at 6:12
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
    Commented Nov 28, 2016 at 10:14

You must log in to answer this question.

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