Skip to main content
added 587 characters in body
Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

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$.

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).

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$.

Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

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).