Abstract
A binary (cyclic) Gray code is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube.
Fink showed that every perfect matching in the n-dimensional hypercube Q(n) can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the "path version" of this problem.
Namely, we characterize when a perfect matching in Q(n) extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in Q(n) with two faulty vertices extends to a Hamiltonian cycle.
In both cases we show that for all dimensions n >= 5 the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras' conjecture with an additional edge, or with two faulty vertices.
The proof for the case n = 5 is computer-assisted.