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 alpha, beta is an element of{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) is an element of{0,1}(n): if d(alpha(i), beta(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 alpha(i) to beta(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 alpha(i), beta(i) is an element of{0,1}(n) with d(alpha(i), beta(i)) odd for which such sequences do not exist. (C) 2017 Elsevier B.V. All rights reserved.