2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Counting Hamilonian cycles is hard -- knowing even whether there is one or not is NP-complete, and I can't imagine that (hypothetically) knowing there is at least one makes finding the number of cycles easier. $\endgroup$ – Henning Makholm Apr 20 at 12:44
5
+50
$\begingroup$

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$, there exist 6-regular graphs on 16 vertices which are not Hamiltonian, even if we restrict to connected graphs.

(For example, take a copy of $K_8$ (the complete graph on 8 vertices) with antipodal edges removed: this is 6-regular. 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.) A non-Hamiltonian 6-regular 16-graph

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$, 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.

For $n=4$, there are $113\,314\,233\,808$ connected 6-regular graphs on 16 vertices. Mathematica has 17 of these 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).$$

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. (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).)

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:

3 by 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.

$\endgroup$
  • $\begingroup$ This is very helpful. Clarifying questions: 1) The image of the rook graph seems to indicate a clique and not a Hamiltonian cycle for all nine vertices. I'd like to confirm what the "cases" are and why they are clustered in case sets of varying order for the n=3 distinct Hamiltonian cycles. 2) If someone does not have access to the GraphData database, may the numbers of cycles indicated be used to reconstitute the sequences to which they refer, or are they just for index use? $\endgroup$ – bblohowiak Apr 26 at 12:04
  • $\begingroup$ @bblohowiak: I just got the image from Wikipedia, the emphasized lines aren't important. For the cases, I just meant that there are two 4-regular graphs on 9 vertices with 40 Hamiltonian cycles, and there are three 4-regular graphs on 9 vertices with 44 Hamiltonian cycles, and so on. 2) Those numbers are just the number of distinct Hamiltonian cycles. As you can see, for the graphs on 16 vertices, there are a very large number! They can't really help in finding any particular cycles, except that if you're trying to enumerate all the cycles, you'll know when you're done. $\endgroup$ – Kundor Apr 26 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.