Darko Dimitrov ; Tomáš Dvořák ; Petr Gregor ; Riste Škrekovski - Gray codes avoiding matchings

dmtcs:457 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, Vol. 11 no. 2 - https://doi.org/10.46298/dmtcs.457
Gray codes avoiding matchingsArticle

Authors: Darko Dimitrov 1; Tomáš Dvořák ORCID2; Petr Gregor ORCID2; Riste Škrekovski ORCID3

  • 1 Institut für Informatik [Berlin]
  • 2 Faculty of Mathematics and Physics [Praha/Prague]
  • 3 Oddelek za Matematiko

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.


Volume: Vol. 11 no. 2
Section: Graph and Algorithms
Published on: January 1, 2009
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 348 times.
This article's PDF has been downloaded 468 times.