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 <>
Submitted on : Wednesday, May 7, 2014 - 4:17:20 PM
Last modification on : Friday, March 15, 2019 - 4:55:06 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

  • HAL Id : hal-00988206, version 1

Collections

Citation

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

Share

Metrics

Record views

484

Files downloads

1010