Least graph with exactly $2014$ hamiltonian circuits?

80 Views Asked by At
  • What is the least graph with exactly $2014$ hamiltonian circuits ?

First of all, I am not sure, if for every natural number $n$, there is a graph with exactly $n$ hamiltonian circuits. Is that so, and if yes, how can it be proven ? If no, for which numbers does no graph exist ?

I used an online graph theory program to check the graphs with $9$ nodes or less. I found $3$ graphs with $9$ nodes and $2016$ hamiltonian circuits, but none with $2012-2015$ hamiltonian circuits. The cubic graphs upto $18$ vertices have less then $2000$ hamiltonian circuits.

1

There are 1 best solutions below

3
On BEST ANSWER

This is an answer for question in the title. I claim that the least such graph has $10$ nodes (assuming the data from the comment, stating that there is a graph with $9$ nodes which has exactly $2014$ hamiltonian paths).

If there is a graph $G$ on $v$ vertices with $N$ Hamiltonian paths, we can add a new vertex and connect it with all vertices from $G$. This will produce a graph on $v+1$ vertices with $N$ Hamiltonian circuits. So, in particular, there is a graph on $10$ vertices with exactly $2014$ Hamiltonian circuits. This graph is minimal because, as it is mentioned in the question, no graph with $9$ nodes or less satisfies this property.

Since the cycle of length $h$ has exactly $h$ Hamiltonian paths, these considerations answer the second question as well.