Wednesday 23 January 2008

co.combinatorics - Hamilton cycle decompositions of the complete graph

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][1]<>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[1]:=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)!.

No comments:

Post a Comment