Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the following: Let $Q:=\{1,2,\cdots q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge between $(a_1,a_2,\cdots a_n)$ and $(b_1,b_2,\cdots b_n)$ if and only if $a_i\ne b_i$ for exactly one value of $i$. Show that $G$ is Hamiltonian.

I tried a few cases for n. For n=1 we have a complete graph and for n=2 I found an Hamiltonian circuit 11-13-12-32-22-21-23-33-31-11. However this isnt helping me. Any help please.

share|improve this question
4  
(Assuming this is not homework…) Your graph $G$ is known as the Hamming graph $H(n,q)$. One (class of) Hamiltonian circuit is given by the Gray code, specifically, the $(q,n)$-Gray code. You can look at one such construction and try proving that it works. –  ShreevatsaR Jun 6 '11 at 12:17
    
Hmm...I really am trying to understand the algorithm at the moment. (a few pointers would be helpful). Is it possible to present the algorithm in simpler terms, like by using induction. This is not homework. –  Shahab Jun 7 '11 at 6:21
    
Yes indeed :) Thanks. –  Shahab Jun 8 '11 at 4:46

1 Answer 1

up vote 1 down vote accepted

Ok, here's one method that works. (I didn't try to understand the code on Wikipedia. :-))

As said in the comment, the graph $G$ with $\{1,\dots,q\}^n$ as vertices and an edge between strings that differ in exactly one place is known as the Hamming graph $H(n,q)$. A Hamiltonian path/cycle in such a graph is called a $(q,n)$-Gray code: it is a sequence of $q^n$ strings in which each pair of successive strings differ in exactly one place. (For a Hamiltonian cycle, you want that the first and last strings also differ in exactly one place.)

The case where $q=2$ is simple and illustrative: one popular Gray code, called the reflected binary code is constructed as follows: for $n=1$, you write down the sequence $(1, 2)$. For $n>1$, write down the sequence for $n-1$, reflect it (write down the elements of the sequence in reverse order), then append $1$ to each elements of the original sequence and $2$ to each element of the reflected sequence. Thus for $n=2$, you take the sequence for $n=1$ (namely $(1, 2)$), reflect it (so $(2, 1)$), etc., to get $(11, 12, 22, 21)$. Let's use the notation that $a\{S\}$ means the sequence of values $ax$ for $x$ in $S$. (Like Unix shell expansion syntax. Hope this isn't confusing.) For $n=3$, you get $(1\{11, 12, 22, 21\}, 2\{21, 22, 12, 11\})$. Etc.

For general $q$, when $q$ is even, exactly the same algorithm works: to get the sequence for $n$, make $q$ copies of the sequence for $n-1$, in which alternate ones are reflected, and append a different first symbol to each. For instance for $q=4$, start with $(1, 2, 3, 4)$ for $n=1$, then for $n=2$ you have $(1\{1,2,3,4\},2\{4,3,2,1\},3\{1,2,3,4\},4\{4,3,2,1\})$, etc. Unfortunately, for odd $q$, you get a Hamiltonian path that is not a Hamiltonian cycle. For $q=3$ for instance, you start with $(1, 2, 3)$ for $n=1$ and for $n=2$ you get $(1\{1,2,3\}, 2\{3,2,1\}, 3\{1, 2, 3\})$ in which the first and last strings $11$ and $33$ are not adjacent.

To fix this, we can use rotation instead of reflection. Given a sequence $S$ of strings, let $r(S)$ denote the sequence in which the first symbol of each string is decreased by $1 \pmod q$. Observe that if a sequence $S$ is a valid Gray code / valid path in the Hamming graph, then so is $r(S)$ — for any two adjacent strings in $S$, if their first symbols are the same then so are the first symbols of their corresponding strings in $r(S)$, and if the first symbols are distinct (and everything else the same), then so are they in $r(S)$. We can define the $(q,n)$-Gray code as follows:

  • For $n=1$, take $(1, 2, \dots, q)$.

  • For $n>1$, let $S$ be a $(q, n-1)$-Gray code. Then take $(1\{S\}, 2\{r(S)\}, \dots, q\{r^{q-1}(S)\})$

To illustrate this for $q=5$:

  • For $n=1$, take $(1, 2, 3, 4, 5)$.

  • For $n=2$, take $(1\{1, 2, 3, 4, 5\}, 2\{5, 1, 2, 3, 4\}, 3\{4, 5, 1, 2, 3\}, 4\{3, 4, 5, 1, 2\}, 5\{2, 3, 4, 5, 1\})$. You have a path from $11$ to $51$, which for convenience I'll denote $11 \to 51$.

  • For $n=3$, take $(1 \{ 11 \to 51\}$, $2\{51 \to 41\}$, $3\{41 \to 31\}$, $4\{31 \to 21\}$, $5\{21 \to 11\})$. So you have a path from $111$ to $511$.

To restate the whole thing in graph-theoretic terms: observe that the Hamming graph $H(n,q)$ consists of $q$ copies of $H(n-1,q)$, with additional edges between vertices that correspond to the same vertex in $H(n-1,q)$. Your Hamiltonian cycle is a Hamiltonian path in the first copy, followed by a Hamiltonian path (starting from its neighbour) in the second copy, followed by a Hamiltonian path in the third copy, etc. You just have to arrange things so that you end at a neighbour of where you start.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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