Generalized Gray codes with prescribed ends

Abstract

An $n$-bit Gray code is a sequence of all $n$-bit strings such that consecutive strings differ in a single bit. It is well-known that given $\alpha ,\beta \in \{0,1{\}}^n$, an $n$-bit Gray code between $\alpha$ and $\beta$ exists iff the Hamming distance $d(\alpha ,\beta )$ of $\alpha$ and $\beta$ is odd. We generalize this classical result to $k$ pairwise disjoint pairs ${\alpha }_i,{\beta }_i\in \{0,1{\}}^n$: if $d({\alpha }_i,{\beta }_i)$ is odd for all $i$ and $k<n$, then the set of all $n$-bit strings can be partitioned into $k$ sequences such that the $i$-th sequence leads from ${\alpha }_i$ to ${\beta }_i$ and consecutive strings differ in a single bit. This holds for every $n>1$ with one exception in the case when $n=k+1=4$. Our result is optimal in the sense that for every $n>2$ there are $n$ pairwise disjoint pairs ${\alpha }_i,{\beta }_i\in \{0,1{\}}^n$ with $d({\alpha }_i,{\beta }_i)$ odd for which such sequences do not exist.

30 pages, 2 figures

References in corpus (1)

• Generalized Gray codes with prescribed ends of small dimensions