How to calculate quantity of Hamilton cycles

Question

If I have $n^2$ vertices and each vertex is adjacent to $2n-2$ vertices, how may I calculate the quantity of possible Hamilton cycles?

Would I need to modify the computation if I stipulated that I'm only interested in the cycles that begin and end at a specific vertex? What if I'm only interested in the cycles of the previous sentence that also share their second vertex in common?

Answer 1

Just knowing the number of vertices and their degrees isn't enough information to tell the number of Hamiltonian cycles, or even whether the graph has one. The single such graph for $n=2$, and the 16 examples for $n=3$, all happen to be Hamiltonian, but for $n=4$, seven of the 113 314 233 808 connected 6-regular graphs on 16 vertices are not Hamiltonian at all^*.

Among the graphs which are Hamiltonian, the number of distinct cycles varies:

• For $n=2$, the graph is a 4-cycle, with a single Hamiltonian cycle.

• For $n=3$, the number of Hamiltonian cycles is between 36 and 64^†.

• For $n=4$, the number is between 0 and at least 1 011 713^‡.

So obviously no formula depending only on $n$ can tell you the number of Hamiltonian cycles.

However, there is a formula for the number of Hamiltonian cycles in any graph. Let $N = n^2$ be the number of vertices, $\bar{N}$ be $\{1,\dots,N\}$, $\binom{\bar{N}}{i}$ be the subsets of $\bar{N}$ of size $i$, $A$ be the adjacency matrix of the graph, and $A_S$ the submatrix with its row and column indices in the set $S$ (a principal submatrix.)

Then the number of Hamiltonian cycles is $$ c_N = \frac{1}{2N} \sum_{i=2}^N (-1)^{N-i} \sum_{S \in \binom{\bar{N}}{i}} \operatorname{Tr}(A_S^N) $$ where $A_S^N$ means the submatrix $A_S$ to the $N$th power^§.

Of course, every Hamiltonian cycle goes through every vertex, so saying they "begin and end at a specific vertex" changes nothing: you can consider any of the cycles to begin and end at any vertex you choose.

Counting Hamiltonian cycles which include an edge from a specific vertex $u$ to a specific vertex $v$ can be accomplished by modifying the adjacency matrix used in the formula. Essentially, we treat it as a directed graph, with every edge appearing in both directions (so we have 1 in both $a_{ij}$ and $a_{ji}$, the same as the undirected adjacency matrix), except that the only out-edge from $u$ goes to $v$, and the only in-edge at $v$ comes from $u$.

This amounts to changing every entry of $A$ in the row for $u$ and the column for $v$ to 0, except at their intersection; and also changing $a_{vu}$ to 0. Then use the same formula, but without the factor of $\frac{1}{2}$.

To give a concrete example, consider the product graph $K_3 \square K_3$, also known as the $3\times3$ rook graph:

This has adjacency matrix $$ \begin{bmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} $$ Plugging this into the formula for $c_N$, we find it has 48 Hamiltonian cycles.

If we want to require an edge from the first to the second vertex, we modify the adjacency matrix to: $$ \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} $$ (Note the changes in the first row, the second column, and the entry $a_{21}$.) Putting this matrix into the formula, we find there are 24 Hamiltonian cycles including that edge.

For computing the formula, I used this bit of Python code:

import numpy as np
from itertools import combinations
def hamilcount(A):
    N = len(A)
    summ = 0
    for i in range(2, N+1):
        neg = (-1)**(N-i)
        for S in combinations(range(N), i):
            submat = A[np.ix_(S,S)]
            summ += neg * np.linalg.matrix_power(submat, N).trace()
    return summ/2/N

The function takes the adjacency matrix as a Numpy array.

---

Notes

^* For example, take a copy of $K_8$ (the complete graph on 8 vertices) with antipodal edges removed: this is 6-regular. It is also known as the circulant graph $C_8^{1,2,3}$. Now remove two further edges, leaving four vertices with degree 5. Add a copy of $K_7$ with one edge removed: this has 2 vertices of degree 5, and 5 vertices of degree 6. Finally add a new vertex adjacent to the six degree-5 vertices. This is not Hamiltonian.

Originally, I said there were "many" of these non-Hamiltonian graphs, since I came up with the above example pretty quickly. I became suspicious about this and checked with genreg and the nauty gtools: it turns out there are only 7, all of them variations on the above. The two additional edges removed from $C_8^{1,2,3}$ can be chosen in 3 non-isomorphic ways; or two additional edges can be removed from $K_7$, and only one edge from $C_8^{1,2,3}$; or the 8-vertex side can be this guy:

(which has two vertices of degree 5, and six vertices of degree 6), or one of its subgraphs removing one edge.

^† There are sixteen 4-regular graphs on 9 vertices, and they have 36, 40 (2 cases), 41, 43, 44 (3 cases), 46, 47, 48 (3 cases), 52, 55, or 64 distinct Hamiltonian cycles, according to Mathematica.

^‡ There are 113 314 233 808 connected 6-regular graphs on 16 vertices. We showed above that some of them have no Hamiltonian cycles.

Mathematica has 17 of these graphs in its GraphData database, and their numbers of distinct Hamiltonian cycles are:

(235 832, 279 293, 350 392, 351 953, 278 864, 278 616, 1 011 713, 347 037, 503 168, 1 010 528, 1 009 920, 276 768, 273 808, 350 484, 284 112, 281 232, 276 816).

^§ The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths by S.N. Perepechko and A.N. Voropaev, 2012 (Russian).