### 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 2

^{n}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 Q_{n}, and a cyclic Gray code as a Hamiltonian cycle of Q_{n}. 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 Q_{n}, 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, Q_{n}has a (cyclic) Gray code that avoids M if and only if Q_{n}-M is a connected graph. This complements a recent result of Fink, who proved that every perfect matching of Q_{n}can be extended to a Hamiltonian cycle. Furthermore, our results imply that the problem of Hamiltonicity of Q_{n}with faulty edges, which is NP-complete in general, becomes polynomial for up to 2^{n-1}edges provided they form a matching.Full Text: PDF PostScript