Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs? It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles.


  What are the best known upper bound and lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs? Given a cubic Hamiltonian graph, What is the complexity of finding the number of Hamiltonian cycles? Is it #$P$-hard?
In my paper "The traveling salesman problem for cubic graphs" (J. Graph Algorithms and Applications 11(1):61-81, 2007) I proved an upper bound of $2^{3n/8}$ on the number of Hamiltonian cycles, conjectured that the bound could be improved to $2^{n/3}$, and found a family of graphs that have exactly $2^{n/3}$ showing that, if true, the conjectured bound would be tight. Heidi Gebauer ("On the Number of Hamilton Cycles in Bounded Degree Graphs", ANALCO 2008) improved the upper bound to $1.276^n$.

If one allows multigraphs then a cycle that alternates between single and double bonds has $2^{n/2}$ Hamiltonian cycles, and this is tight.