Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?
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.