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\ge 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.
@article{10_37236_6928,
author = {Petr Gregor and Tom\'a\v{s} Novotn\'y and Riste \v{S}krekovski},
title = {Extending perfect matchings to {Gray} codes with prescribed ends},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/6928},
zbl = {1391.05145},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6928/}
}
TY - JOUR
AU - Petr Gregor
AU - Tomáš Novotný
AU - Riste Škrekovski
TI - Extending perfect matchings to Gray codes with prescribed ends
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6928/
DO - 10.37236/6928
ID - 10_37236_6928
ER -
%0 Journal Article
%A Petr Gregor
%A Tomáš Novotný
%A Riste Škrekovski
%T Extending perfect matchings to Gray codes with prescribed ends
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6928/
%R 10.37236/6928
%F 10_37236_6928
Petr Gregor; Tomáš Novotný; Riste Škrekovski. Extending perfect matchings to Gray codes with prescribed ends. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/6928
