Number of Hamiltonian cycles in incomplete graphs?

Question

Assuming an uncomplete undirected graph $G$:

1. Is there a formula to compute the number Hamiltonian cycles in $G$?
2. Or, do we know anything about the minimum or maximum Hamiltonian cycles $G$ could contain?

Answer 1

If all you know is that $G$ is not a clique, then the number of Hamilton cycles could be as large as the number for $K_n-\text{edge}$. For this graph, we can compute the number of hamilton cycles easily. The number of directed hamilton cycles in $K_n$ is $(n-1)!$ and the number of directed hamilton cycles that used the edge, say, $1\to 2$ or $2\to 1$ is $2(n-2)!$. Thus, the number of (undirected) hamilton cycles in $K_n-\text{edge}$ is ${1\over 2}\bigl((n-1)!-2(n-2)!\bigr)={(n-2)!(n-3)\over 2}$.

Just determining whether or not a graph has a Hamilton cycle is NP-complete, so asking for a formula for a general graph is way too optimistic. In order to ask for upper and lower bounds, you should put more restrictions on the graph.

For instance, we know that if $\delta(G)\geq |V(G)|/2$, then $G$ is hamiltonian. It is reasonable to ask how many hamilton cycles such a graph must have. Indeed, this is considered in the paper ``On the number of Hamilton cycles in Dirac graphs'' by Sarkozy et al.

It is also reasonable to ask for an upper bound on the number of hamilton cycles in a graph if we, say, bound the number of edges. This question was considered in the paper ``The maximum number of Hamiltonian cycles in graphs with a fixed number of vertices and edges'' by Teunter et al.