Hamilton cycle decompositions of the complete graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:46:43Z http://mathoverflow.net/feeds/question/10577 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph Hamilton cycle decompositions of the complete graph Douglas S. Stones 2010-01-03T10:37:22Z 2010-10-02T19:11:10Z <p>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).</p> <p>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)&lt;\alpha^{-1}(1)$. We also write the decomposition $\alpha\beta\ldots$ such that $\alpha(1)&lt;\beta(1)&lt;\cdots$.</p> <p>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$.</p> http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph/10616#10616 Answer by Emil for Hamilton cycle decompositions of the complete graph Emil 2010-01-03T20:06:12Z 2010-01-04T00:13:36Z <p>In <a href="http://www.cas.mcmaster.ca/~franek/journals/twofact.ps" rel="nofollow">Two-factorizations of complete graphs</a> it is stated that $K_9$ has 122 <em>non-isomorphic</em> Hamiltonian decompositions, and the corresponding number for $K_{11}$ is 3140 (<strong>EDIT</strong>: 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.)</p> <p>Now you are interested in the labeled case, which may be easier. However I have not been able to find anything (on Google).</p> http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph/10618#10618 Answer by Harrison Brown for Hamilton cycle decompositions of the complete graph Harrison Brown 2010-01-03T20:34:00Z 2010-01-03T23:14:26Z <p>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.</p> <p>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.</p> <p>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 <strong>hamcyc</strong>, and then compute</p> <p><strong>partitions</strong> := Subsets[hamcyc, (n-1)/2].</p> <p>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.)</p> <p>Multiply this count by n!/(n-1) to get the number of partitions into Hamiltonian cycles.</p> http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph/27909#27909 Answer by Douglas S. Stones for Hamilton cycle decompositions of the complete graph Douglas S. Stones 2010-06-12T06:39:22Z 2010-06-12T06:39:22Z <p>Just reporting that I wrote another algorithm for this and found the following values:</p> <pre><code>3 1 5 6 7 960 9 40037760 </code></pre> <p>I ran this through the superseeker on Sloane and it came up with nothing (so perhaps nobody has counted these before).</p> <p>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.</p> <pre><code>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&lt;3) then return fail; fi; if(j=1) then A:=[Minimum(Filtered([2..n],i-&gt;ForAll([1..n-1],t-&gt;L[t][1]&lt;&gt;i)))]; else A:=Filtered([1..n],s-&gt;ForAll([1..n-1],t-&gt;L[t][j]&lt;&gt;s) and ForAll([1..n],t-&gt;L[i][t]&lt;&gt;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&lt;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&lt;3) then return fail; fi; if(n=3) then return 1; fi; L:=List([1..n-1],i-&gt;List([1..n],j-&gt;0)); L[1]:=List([1..n],i-&gt;i mod n+1); L[1+(n-1)/2]:=ListPerm(Inverse(PermList(List([1..n],i-&gt;i mod n+1)))); return Factorial(n-2)*EnumerateHamiltonDecompositionsBacktrackingAlgorithm(n,L,n+1); end;; </code></pre> <p>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)!.</p> http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph/40864#40864 Answer by Estera for Hamilton cycle decompositions of the complete graph Estera 2010-10-02T19:11:10Z 2010-10-02T19:11:10Z <p>How do i write the number of different Hamiltonian cycles there are in a fully connected graph with n vertices? </p>