3
$\begingroup$
  • 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.

$\endgroup$
  • $\begingroup$ $18$ graphs with $9$ nodes have exactly $2014$ hamiltonian paths. $\endgroup$ – Peter Oct 16 '14 at 21:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice! So, the additional question can be reduced to the problem of finding graphs with $n$ hamiltonian paths. $\endgroup$ – Peter Oct 16 '14 at 22:15
  • $\begingroup$ It remains to determine which is the least number of edges. $\endgroup$ – Peter Oct 16 '14 at 22:18
  • 1
    $\begingroup$ Yes. And we can note that $n$-cycles satisfy this property (as to the second question). $\endgroup$ – user2097 Oct 16 '14 at 22:18

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.