Do the two order-4 Latin square graphs have the same number of Hamilton cycles?

78 Views Asked by At

A Latin square graph of a Latin square $L=(L_{ij})$ of order $n$ has $n^2$ vertices $(i,j)$ and edges between distinct vertices $(i,j)$ and $(i',j')$ whenever (a) $i=i'$, (b) $j=j'$, or (c) $L_{ij}=L_{i'j'}$. They give a family of strongly regular graphs.

Up to paratopism, there are two Latin squares of order $4$. They can be thought of the addition tables of $\mathbb{Z}_4$ and $\mathbb{Z}_2 \times \mathbb{Z}_2$. McKay lists these two representatives:

0123
1032
2301
3210

0123
1032
2310
3201

Question: Do their corresponding Latin square graphs have the same number of Hamilton cycles?

I wrote some simple code to count Hamilton cycles, but it's too slow to finish the enumeration. Maybe I could improve it, but I'm thinking there might be a better way to answer the question (e.g. using the fact that the Latin squares above only differ in 4 cells).