0
$\begingroup$

A complete directed graph with n nodes has n(n-1) edges. Since each node has in-degree = out-degree = (n-1) and the graph is strongly connected, there must exist an Euler path. Since there are n nodes, a Hamilton path must have length (n-1). Now, the question is: For which values of n can this Euler path of length n(n-1) be partitioned into n distinct Hamilton paths of length (n-1)?

This obviously works for n = 2: The Euler path of length 2(2-1) = 2 is "0 -> 1 -> 0", and it can be partitioned into 2 Hamilton paths of length (2-1) = 1: "0 -> 1" and "1 -> 0".

I didn't find any combination that works for n = 3 or n = 4.

Does there even exist a larger n for which this works? I am completely stuck, since I relied on brute force so far. Is there a smart criterion or algorithm for this?

EDIT: A "partitioning" in this context means that each Hamiltonian path consists of consecutive edges of the Euler path, such that each edge of the Euler path is contained in exactly one Hamiltonian path, and all the Hamiltonian paths can be appended to each other in such a way that the result is the original Euler path.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "partitioning" an Euler path? In any event, I suggest you think about prime values of n. $\endgroup$ – Matthew Daly Aug 10 at 23:56
  • $\begingroup$ To clarify, when you ask whether the Euler path can be partitioned into Hamilton paths, are you requiring the Hamilton paths to all be contiguous in the original Euler path? (therefore requiring the first (n-1) edges to be a Hamilton path, the next (n-1) edges to be a Hamilton path, etc.) $\endgroup$ – Brian Moehring Aug 10 at 23:56
  • $\begingroup$ By "partitioning" I mean that the edges from the Euler path are distributed among the Hamilton paths so that each edge in the Euler path is used in exactly one Hamilton path. And since the Hamilton paths must be internally consecutive, I think this implies that the first (n-1) edges must go to the first Hamilton path, the next (n-1) edges to the second, and so on. EDIT: Further clarification: The Euler path is not given. I can assume any Euler path of the complete directed graph as a basis for the partitioning. $\endgroup$ – Nico Schaumberger Aug 11 at 0:00
  • $\begingroup$ It would be clearer to describe this without Euler paths then. You want to know if the arcs of a complete directed graph can be partitioned into Hamilton paths. Ignore my previous comment about prime n; I imagined you were thinking about Hamilton cycles. Off the top of my head, a partition into Hamilton paths would work for n=4, so try checking that again. $\endgroup$ – Matthew Daly Aug 11 at 0:13
  • $\begingroup$ ...You are right, there is a partitioning for n = 4: "1 -> 2 -> 3 -> 4", "4 -> 3 -> 2 -> 1", "2 -> 4 -> 1 -> 3" and "3 -> 1 -> 4 -> 2", if I'm not mistaken. I just didn't see it, because these Hamilton paths aren't using consecutive edges on the Euler path. The Euler path was a trap all along, and now I feel silly. $\endgroup$ – Nico Schaumberger Aug 11 at 0:26
0
$\begingroup$

I am completely stuck, since I relied on brute force so far. Is there a smart criterion or algorithm for this?

There's brute force and brute force.

There's an obvious bijection between Hamiltonian paths and permutations of the vertices.

Without loss of generality, the first Hamiltonian path can correspond to the identity permutation.

Then a simple search, where we merely track the unvisited vertices in the current Hamiltonian path and the edges which have already been used, quickly (in a matter of a few seconds) finds solutions for $n \in \{2,6,7,8,9\}$:

0, 1, 0

0, 1, 2, 3, 4, 5, 0, 2, 1, 4, 3, 0, 4, 1, 5, 2, 4, 0, 3, 5, 1, 3, 2, 0, 5, 4, 2, 5, 3, 1, 0

0, 1, 2, 3, 4, 5, 6, 0, 2, 1, 3, 5, 4, 0, 3, 1, 6, 2, 5, 0, 4, 3, 2, 6, 1, 5, 3, 0, 6, 4, 2, 0, 5, 1, 4, 6, 3, 6, 5, 2, 4, 1, 0

0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 5, 4, 6, 0, 3, 1, 4, 2, 7, 5, 0, 4, 1, 6, 3, 7, 2, 0, 5, 3, 6, 1, 7, 4, 3, 0, 6, 2, 5, 7, 1, 5, 2, 6, 4, 0, 7, 3, 2, 4, 7, 6, 5, 1, 0

0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 2, 1, 3, 5, 4, 7, 6, 0, 3, 1, 4, 2, 5, 8, 7, 0, 4, 1, 5, 2, 6, 8, 3, 0, 5, 1, 7, 2, 8, 6, 4, 0, 6, 1, 8, 5, 7, 3, 2, 4, 6, 3, 8, 1, 0, 7, 5, 0, 8, 4, 3, 6, 2, 7, 1, 6, 5, 3, 7, 4, 8, 2, 0

and excludes solutions for $n \in \{3,4,5\}$. My program is still searching for $n=10$ after 5 minutes.

$\endgroup$
  • $\begingroup$ Ok, so in other words I just have to ask a program to find solutions for me. This is what I will do then. Thanks. $\endgroup$ – Nico Schaumberger Aug 11 at 21:15
  • $\begingroup$ @NicoSchaumberger, to be clear, I'm not saying that this is the most efficient way to approach the problem. Just that it's efficient enough to get further than you already had. $\endgroup$ – Peter Taylor Aug 12 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.