Generalized Gray codes with prescribed ends

An n-bit Gray code is a sequence of all n-bit vectors such that consecutive vectors differ in a single bit. It is well-known that given α, β ∈ { 0, 1 } n, an n-bit Gray code between α and β exists iff the Hamming distance d ( α, β ) of α and β is odd. We generalize this classical result to k pairwise disjoint pairs α i, β i ∈ { 0, 1 } n: if d ( α i, β i ) is odd for all i and k < n, then the set of all n-bit vectors can be partitioned into k sequences such that the i-th sequence leads from α i to β i and consecutive vectors 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 α i, β i ∈ { 0, 1 } n with d ( α i, β i ) odd for which such sequences do not exist.

Authors

• Tomáš Dvořák
• Petr Gregor
• Václav Koubek

Keywords

• Gray code
• Hamiltonian path
• Hypercube
• Path partition
• Disjoint path cover
• Prescribed endvertices