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 the number of Hamiltonian cycles in cubic Hamiltonian graphs?
cc.complexity theory;counting complexity
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 Likiewicz, 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 Likiewicz, Mitsunori Ogihara and Seinosuke Toda.  The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.  Theoretical Computer Science, 304(13):129156, July 2003.  http://dx.doi.org/10.1016/S0304-3975(03)00080-X