Skip to Main content Skip to Navigation
Journal articles

Gray codes avoiding matchings

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 Hamilionicity 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00988206
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, May 7, 2014 - 4:17:20 PM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Thursday, August 7, 2014 - 11:36:11 AM

File

1310-4767-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Darko Dimitrov, Tomáš Dvořák, Petr Gregor, Riste Škrekovski. Gray codes avoiding matchings. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, Vol. 11 no. 2 (2), pp.123--147. ⟨10.46298/dmtcs.457⟩. ⟨hal-00988206⟩

Share

Metrics

Record views

105

Files downloads

758