Gray Codes Avoiding Matchings
Darko Dimitrov, Tomáš Dvořák, Petr Gregor, Riste Škrekovski
Abstract
A (cyclic) n-bit Gray code is a (cyclic) ordering of
all 2n binary strings of length
n such that consecutive strings differ in a single
bit. Equivalently, an n-bit Gray code can be viewed as
a Hamiltonian path of the n-dimensional hypercube
Qn, and a cyclic Gray code as a Hamiltonian
cycle of Qn. In this paper we study
(cyclic) Gray codes avoiding a given set of faulty edges that form a
matching. Given a matching M and two vertices
u,v of Qn, n≥4,
our main result provides a necessary and sufficient condition,
expressed in terms of forbidden configurations for M,
for the existence of a Gray code between u and
v that avoids M. As a corollary, we obtain
a similar characterization for a cyclic Gray code avoiding
M. In particular, in the case that M is a
perfect matching, Qn has a (cyclic) Gray
code that avoids M if and only if
Qn-M is a connected graph. This complements
a recent result of Fink, who proved that every perfect matching of
Qn can be extended to a Hamiltonian
cycle. Furthermore, our results imply that the problem of
Hamiltonicity of Qn with faulty edges, which
is NP-complete in general, becomes polynomial for up to
2n-1 edges provided they form a matching.
Full Text: PDF PostScript