Count Hamiltonian Cycles in directed torus graph Here we define "torus graph" to be a directed graph with vertex set $V=\mathbb Z_n\times\mathbb Z_m$ and edge set $$E=\{(x,y)\to(x+1,y)\mid(x,y)\in V\}\\\cup\{(x,y)\to(x,y+1)\mid(x,y)\in V\}$$For example, when $n=1,m=2$, the graph has two vertices: $(0,0)$ and $(0,1)$, and four edges: $(0,0)\to(0,0),(0,1)\to(0,1),(0,0)\to(0,1),(0,1)\to(0,0)$.
I want to find the number of Hamilton Cycles in this graph. When $n=m$, I find that (without proof) the answer is A056188：$ 1, 2, 6, 8, 30, 12, 126, 128, 342, 260\dots$ But I can't find more useful properties. Any help would be appreciated.
 A: The paper When the product of directed cycles is Hamiltonian by Erdös and Trotter (https://doi.org/10.1002/jgt.3190020206) discusses this very problem.
A Hamiltonian cycle can only exist if $n$ and $m$ are not coprime. Letting $d=\gcd(n,m)$, it is further necessary that there exist integers $d_1,d_2>0$ so that

*

*$d_1+d_2=d$, and


*$\gcd(n,d_1)=\gcd(m,d_2)=1$.
These conditions are also sufficient. Specifically, they show that any Hamiltonian cycle in $\mathbb Z_n\times \mathbb Z_m$ is completely determined by its first $d$ steps, which must bring the path to a point $(d_1,d_2)$ which satisfy the above conditions. All of the $\binom{d}{d_1}$ ways to reach $(d_1,d_2)$ can be uniquely extended to a Hamiltonian cycle. Therefore, the number of Hamiltonian cycles is the sum of $\binom{d}{d_1}$ over all pairs $(d_1,d_2)$ satisfying the conditions. This agrees with your OEIS link.
For example (lifted from the same paper), $\Bbb Z_{40}\times \Bbb Z_{56}$ is Hamiltonian. We must chose $(d_1,d_2)$ summing to $d=\gcd(40,56)=8$, so that $d_1$ is coprime to $40$ and $d_2$ is coprime to $56$. It turns out the only possibilities are $(3,5)$ and $(7,1)$. Therefore, the number of paths is $\binom83+\binom87=64$.
