Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
Counting Hamiltonian circuits in a 3-regular Hamiltonian graph is #P-complete, as follows.
Proof sketch. The membership in #P is trivial, so we will only show the #P-hardness.
Section 3 of Liśkiewicz, Ogihara and Toda [LOT03] shows that counting Hamiltonian circuits in a 3-regular (and in fact planar at the same time) graph is #P-complete. Moreover, their reduction from #3SAT maps satisfiable 3CNF formula to Hamiltonian graphs. Therefore, you can reduce #3SAT to counting Hamiltonian circuits in a 3-regular Hamiltonian graph by first adding one trivial solution to a given 3CNF formula and then reducing it to counting Hamiltonian circuits by using the reduction in [LOT03]. QED.
[LOT03] Maciej Liśkiewicz, Mitsunori Ogihara and Seinosuke Toda. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science, 304(1–3):129–156, July 2003. http://dx.doi.org/10.1016/S0304-3975(03)00080-X
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.
Some graphs have exactly three hamiltonian circuits:
http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract
If one starts with the plane graph of the tetrahedron, which contains exactly three hamiltonian circuits, and creates a new planar 3-connected graph by truncating a single vertex one gets a new graph which has exactly three hamiltonian circuits. If one continues to truncate one vertex at a time one gets a family of graphs with exactly three hamiltonian circuits.
Additional comment:
There also has been some work on the question of which graphs other than cycles have exactly one hamiltonion circuit:
http://www3.interscience.wiley.com/journal/113386600/abstract
A very nice survey paper about hamltionian circuits in special kinds of graphs which has a section dealing with numbers of hamiltonian circuits, and corrects some problems with the paper above is:
