Skip to main content
added 12 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.

What is the maximum number of edge-disjoint directed HamiltonHamiltonian cycles of $K_{n}^{*}$?

For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ HamiltonHamiltonian cycles, and hence $K_n^*$ can be decomposed into $2k$ directed HamiltonHamiltonian cycles.

For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1$.$n-1.$ One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed HamiltonHamiltonian cycles.

This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.

What is the maximum number of edge-disjoint directed Hamilton cycles of $K_{n}^{*}$?

For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ Hamilton cycles, and hence $K_n^*$ can be decomposed into $2k$ directed Hamilton cycles.

For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1$. One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed Hamilton cycles.

This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.

What is the maximum number of edge-disjoint directed Hamiltonian cycles of $K_{n}^{*}$?

For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ Hamiltonian cycles, and hence $K_n^*$ can be decomposed into $2k$ directed Hamiltonian cycles.

For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1.$ One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed Hamiltonian cycles.

This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.

What is the maximum number of edge-disjoint directed Hamilton cycles of $K_{n}^{*}$?

For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ Hamilton cycles, and hence $K_n^*$ can be decomposed into $2k$ directed Hamilton cycles.

For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1$. One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed Hamilton cycles.

This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.