1
$\begingroup$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry.

I found a Hamilton cycle for $Q_3$ as follows $$000 \to 100 \to 110 \to 010 \to 011 \to 111 \to 101 \to 001 \to 000$$

Now I want to use this cycle to find a Hamiltonian cycle for $Q_4$, I notice that we can split the vertices of $Q_4$ into two groups those that ends with $0$ and those that ends with $1$. If we remove the ending zero from the first group, we are left with the vertices in $Q_3$ and if remove the ending $1$ from the second group we are also left with the vertices in $Q_3$.

I though about just joining the hamiltion cycle that I did for $Q_3$ twice, once where we have the ending is zero and once where we have the ending is $1$

$$000\color{red}{0} \to 100\color{red}{0} \to 110\color{red}{0} \to 010\color{red}{0} \to 011\color{red}{0} \to 111\color{red}{0} \to 101\color{red}{0} \to 001\color{red}{0}$$

and when we have the ending is $1$

$$000\color{blue}{1} \to 100\color{blue}{1} \to 110\color{blue}{1} \to 010\color{blue}{1} \to 011\color{blue}{1} \to 111\color{blue}{1} \to 101\color{blue}{1} \to 001\color{blue}{1}$$

So now If I join them

$$000\color{red}{0} \to 100\color{red}{0} \to 110\color{red}{0} \to 010\color{red}{0} \to 011\color{red}{0} \to 111\color{red}{0} \to 101\color{red}{0} \to \color{green}{001\color{red}{0} \to 000\color{blue}{1}} \to 100\color{blue}{1} \to 110\color{blue}{1} \to 010\color{blue}{1} \to 011\color{blue}{1} \to 111\color{blue}{1} \to \color{green}{101\color{blue}{1} \to 001\color{blue}{1}}$$

There is a problem, you it doesn't differ by $1$ any more when I join them (See the green coloured ones) so how could I fix this to construct a valid hamiltion cycle for $Q_4$

$\endgroup$
  • 2
    $\begingroup$ Do the red path the other way? Go from $0010$ to $0000$ then to $0001$ up to $0011$? $\endgroup$ – Clément Guérin Nov 6 '15 at 8:49
  • $\begingroup$ Start from $1000$ in your red path and then you can use $0000$ as a bridge. $\endgroup$ – cr001 Nov 6 '15 at 8:52
  • $\begingroup$ @ClémentGuérin yeaaaaah , I see now. Thanks a lot, If you put as an answer I will accept it $\endgroup$ – alkabary Nov 6 '15 at 8:55
  • 1
    $\begingroup$ @alkabary: In such simple cases it helps me a lot to draw a picture. You also help other people who are trying to help you if you provide visual support. $\endgroup$ – Moritz Nov 6 '15 at 11:16
  • 2
    $\begingroup$ You might want to read about Gray Codes - specifically binary reflected gray code. They find Hamiltonian cycles in hypercubes. mathworld.wolfram.com/GrayCode.html $\endgroup$ – Manuel Lafond Nov 6 '15 at 16:55

Your Answer

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

Browse other questions tagged or ask your own question.