# Hamilton cycle decompositions of the complete graph

I'm looking for the number of Hamilton cycle decompositions of the labelled complete graph $K_n$ for small $n$. From such a decomposition, we can construct a special type of Latin square (called a row-Hamiltonian Latin square).

Edit: Clearly, we require $n$ to be odd. To ensure that each Hamilton cycle decomposition is counted once, we only include the $n$-cycle permutations $\alpha$ of $\{1,2,\ldots,n\}$ that have $\alpha(1)<\alpha^{-1}(1)$. We also write the decomposition $\alpha\beta\ldots$ such that $\alpha(1)<\beta(1)<\cdots$.

The count for $n=3$ is $1$ counting (123). The count for $n=5$ is $6$, counting the following: $(12345)(13524)$, $(12354)(13425)$, $(12453)(14325)$, $(12435)(13254)$, $(12543)(14235)$ and $(12534)(13245)$. Assuming my code is correct, the count for $n=7$ is $960$.

• Have you tried looking up the first few terms of the sequence in the OEIS? – Qiaochu Yuan Jan 3 '10 at 10:53
• I've tried looking up "Hamilton cycle decompositions" and similar terms in OEIS, Google and MathSciNet without luck. I think the counts for n=3 and n=5 are 1 and 24, respectively (since there are 4! 5-cycles), which is not enough. The count for n=7 seems difficult to compute without coding. But this seems like a very natural question to ask - I'd be surprised if nobody has counted these decompositions before. – Douglas S. Stones Jan 3 '10 at 12:13
• There's a table at mathworld.wolfram.com/HamiltonianCycle.html – Jason Dyer Jan 3 '10 at 13:51
• Jason - that table counts cycles, not decompositions. – Emil Jan 3 '10 at 14:03
• Douglas, are you labeling the cycles in the decomposition as well? So (1 2 3 4 5) (1 3 5 2 4) is not the same as (1 3 5 2 4) (1 2 3 4 5)? – Harrison Brown Jan 3 '10 at 17:23

## 3 Answers

In Two-factorizations of complete graphs it is stated that $K_9$ has 122 non-isomorphic Hamiltonian decompositions, and the corresponding number for $K_{11}$ is 3140 (EDIT: the actual figure is much more than this - see comment). I don't think they know any other values. (Sloane's database does not have any sequences with these numbers in.)

Now you are interested in the labeled case, which may be easier. However I have not been able to find anything (on Google).

• Interesting, it gives some idea of how large the number of $K_9$ is. However, the number for $K_{11}$ counts only those with a non-trivial automorphism. Afterwards "...he generated more than 45 thousand automorphism-free ones before abandoning the task." Perhaps the combinatorial explosion makes this enumeration problem too difficult. – Douglas S. Stones Jan 3 '10 at 22:06

Just reporting that I wrote another algorithm for this and found the following values:

3 1
5 6
7 960
9 40037760


I ran this through the superseeker on Sloane and it came up with nothing (so perhaps nobody has counted these before).

Here's my code below (it uses GAP). We generate a (n-1) x n Latin rectangle where each row is an n-cycle and the i-th and (i+(n-1)/2)-th rows are inverses.

EnumerateHamiltonDecompositionsBacktrackingAlgorithm:=function(n,L,step)
local i,j,k,count,A;
i:=Int((step-1)/n)+1;
j:=(step-1) mod n+1;
count:=0;

if(n mod 2=0 or n<3) then return fail; fi;
if(j=1) then A:=[Minimum(Filtered([2..n],i->ForAll([1..n-1],t->L[t]<>i)))]; else A:=Filtered([1..n],s->ForAll([1..n-1],t->L[t][j]<>s) and ForAll([1..n],t->L[i][t]<>s)); fi;
for k in A do
L[i][j]:=k;
L[i+(n-1)/2][k]:=j;
if((j=n and CycleLengths(PermList(L[i]),[1..n])=[n]) or j<n) then
if(i=(n-1)/2 and j=n) then count:=count+1;
else count:=count+EnumerateHamiltonDecompositionsBacktrackingAlgorithm(n,L,step+1); fi;
fi;
L[i][j]:=0;
L[i+(n-1)/2][k]:=0;
od;
return count;
end;;

EnumerateHamiltonDecompositions:=function(n)
local L;
if(n mod 2=0 or n<3) then return fail; fi;
if(n=3) then return 1; fi;
L:=List([1..n-1],i->List([1..n],j->0));
L:=List([1..n],i->i mod n+1);
L[1+(n-1)/2]:=ListPerm(Inverse(PermList(List([1..n],i->i mod n+1))));
return Factorial(n-2)*EnumerateHamiltonDecompositionsBacktrackingAlgorithm(n,L,n+1);
end;;


The extra data point comes from assuming that (12..n) is one of the cycles, then multiplying the result by (n-2)!. This is legitimate since each decomposition contains a unique cycle with the edge 12, and by permuting the remaining n-2 edges, we generate a unique decomposition with the cycle (12..n). There are no automorphisms under this group action, so each orbit has cardinality (n-2)!.

• I've taken a liberty to submit 1,6,960,40037760 as a new sequence to the OEIS. Soon it will be there as sequence A175554. Further comments/additions are welcome. – Max Alekseyev Jun 29 '10 at 3:07

Gah, I commented but my answer was wrong. I don't have a copy of Mathematica available, but here's (I think) a description of how to compute small cases in Mathematica.

There's a package (Combinatorica) with a function called HamiltonianCycle[graph, All] that returns a list of all the directed Hamiltonian cycles beginning and ending at a single node (as lists). Set the graph to be CirculantGraph[n, {2, 3, ..., (n-1)/2}] and compute this list. This is the graph resulting after we remove the first Hamiltonian cycle.

Now if you're doing Mathematica, it counts directed cycles, so we only want to consider half the lists. Throw out every cycle where the second element is larger than the second-to-last element (the first and last elements are both 1). (N.B. I originally described this step incorrectly, whence the comments.) Create this sublist, which we'll call hamcyc, and then compute

partitions := Subsets[hamcyc, (n-1)/2].

This is a 3D array. Count the number of elements (2D arrays) in this such that every pair of distinct integers in {1, ..., n} is contained as adjacent elements in exactly one of the lists in this 2D array. (Not sure how to do this, but this is the only thing I don't know how to do.)

Multiply this count by n!/(n-1) to get the number of partitions into Hamiltonian cycles.

• I think I get the idea... this would be a fairly memory intensive algorithm. But I should be able to implement it in GAP (I don't have Combinatorica). Also, I'm not sure if you can make the simplification $k \leq (n-1)/2$, for example how would it handle Hamilton cycles like (1723456) when n=7? – Douglas S. Stones Jan 3 '10 at 22:52
• Hm, good point about the simplification, I got confused. I'll fix that. Yeah, it's pretty memory intensive, but I suspect it'll be quick enough to calculate a few examples with n > 5. – Harrison Brown Jan 3 '10 at 23:11