Generalized Gray codes with prescribed ends of small dimensions

Abstract

Given pairwise distinct vertices $\{{\alpha }_i,{\beta }_i{\}}_{i=1}^k$ of the $n$-dimensional hypercube $Q_n$ such that the distance of ${\alpha }_i$ and ${\beta }_i$ is odd, are there paths $P_i$ between ${\alpha }_i$ and ${\beta }_i$ such that $\{V(P_i){\}}_{i=1}^k$ partitions $V(Q_n)$? A positive solution for every $n\ge 1$ and $k=1$ is known as a Gray code of dimension $n$. In this paper we settle this problem for small values of $n$.

8 pages, 2 figures