A cyclic Gray code is an ordered sequence that contains all binary strings of a given length in which each consecutive string differs from the previous one in exactly one coordinate. Such a sequence directly represents a Hamiltonian cycle and path in the hypercube. Ruskey and Savage asked whether every matching in the hypercube extends to a Hamiltonian cycle, and Fink proved that every perfect matching in Formula: see text extends to a Hamiltonian cycle. In this study, we address a problem related to Hamiltonian paths. We prove that every matching at most in five directions where every Formula: see text-cycle contains at least one unsaturated vertex, can be extended to a Hamiltonian path joining two vertices in distinct partite sets of Formula: see text, for Formula: see text. The only forbidden configurations are the so-called half-layers, which form certain natural obstacles.
Ali et al. (Wed,) studied this question.