4
$\begingroup$

Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.

Can we partition the edges of $D$ into $d$ directed Hamiltonian cycles?

An alternative formulation would be to ask whether the hypercube has a so-called directed double cover by Hamiltonian cycles.

For $d\le 2$ the statement holds but quite embarrassingly I'm stuck already at $d=3$.

$\endgroup$
2
  • $\begingroup$ Stand inside the cube center, and look at the corner. Color a vertex black if the three paths go clockwise throuvh the corner, white otherwise. For a Hamiltonian path, each cube face has two black and two white vertices on the face. This should cut down the possibilities to within hand computation. $\endgroup$ Jun 3, 2015 at 23:01
  • 1
    $\begingroup$ Indeed, with such a coloring, one can only have two vertices of the same color joining an edge. This gives that there is no such decomposition for d=3. $\endgroup$ Jun 3, 2015 at 23:30

2 Answers 2

3
$\begingroup$

It looks like the titled question (d=3) is not directly answered: I will hint at how to show the answer is no.

At each vertex, there are two ways that the decomposition can go. I like to call them black or white, or clockwise and counterclockwise. If we look at a cube face and pick all of one type or the other, we induce a path around that face, so not a Hamiltonian path. Similarly, choosing three vertices on a face with the same color/orientation leads to a non Hamiltonian decomposition. So each face has two vertices of each orientation.

However, if we have a path that goes through a white then a black then a white vertex, it will have gone tbrough exactly three vertices of a face, and again will not yield a Hamiltonian path. So each face has to have two adjacent vertices of each color.

But if we have two adjacent faces sharing two vertices of the same color, say black, then a third face adjacent to both will have a white black white coloring which obstructs the decomposition. So not all faces can have the required coloring, so there is no such decomposition into three Hamiltonian paths.

$\endgroup$
5
$\begingroup$

This is what I managed to figure out via google. In "Decompositions into cycles I, Hamilton Decompositions" by Alspach, Bermond and Sotteau (google books link) of 1990, a regular graph $G$ with edge-set $E(G)$ has a Hamilton decomposition if either:

(i) $\text{deg}(G)=2d$ and $E(G)$ can be partitioned into $d$ Hamilton cycles, or

(ii) $\text{deg}(G)=2d+1$ and $E(G)$ can be partitioned into $d$ Hamilton cycles and a perfect matching.

Proposition 1 of that same paper claims that the $n$-cube has a Hamilton decomposition for all $n$. They considered the undirected graph of the hypercube, but it certainly answers your question about $D$ positively when $d$ (in the notation of your question) is even.

Their proof in the even case relies on the fact that the $2m$-cube can be written as a product $C_4\times\cdots\times C_4$ (where $C_4$ is the 4-cycle) and a corollary of a theorem of Aubert and Schneider's:

If $C$ is a cycle and $G$ is a 4-regular graph which is decomposable into two Hamilton cycles, then $C\times G$ can be decomposed into three Hamilton cycles.

I haven't had a chance to think through whether their construction helps in giving you a decomposition of your graph $D$ into Hamiltonian cycles when $d$ is odd. Their construction in that case relies on another paper by Alspach, Heinrich and Liu, "Orthogonal Factorizations of Graphs" which I didn't try to read yet.

It seems that a simple construction for these decompositions for the n-cube is still unknown. I found some discussion of $n=6,8$ in this paper of Okuda and Song.

There are also some slides of Alspach on Hamilton Decompositions which I found here.

$\endgroup$
4
  • $\begingroup$ Hmm, maybe some progress with $d$ odd can be made using the result mentioned in this question? mathoverflow.net/questions/5340 . I guess this is the reference: kam.mff.cuni.cz/~fink/publications/kreweras1.pdf $\endgroup$
    – j.c.
    Jun 3, 2015 at 23:24
  • $\begingroup$ Why does the $d$-cube having a Hamilton decomposition answer the question for all even $d$? I thought the original question required the cycles to use each directed edge once, which would mean assigning a direction to each of the cycles in the decomposition in such a way that each edge is traversed exactly once in each direction? $\endgroup$ Jun 4, 2015 at 8:11
  • 2
    $\begingroup$ @GordonRoyle, double each cycle and orient them in opposite directions. $\endgroup$
    – Ben Barber
    Jun 4, 2015 at 11:32
  • $\begingroup$ @Ben - thanks, I was confusing myself about the actual problem. $\endgroup$ Jun 5, 2015 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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