VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Gray codes avoiding matchings [Elektronski vir]
    Dimitrov, Darko ...
    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 Hamiltonian paths and cycles of ▫$Q_n$▫ avoiding a given set of faulty edges that form a matching, briefly called (cyclic) Gray codes faulting a given matching. Given a matching ▫$M$▫ and two wertices ▫$u,v$▫ of ▫$Q_n$▫, ▫$b \ge 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$▫ faulting ▫$M$▫. As a corollary, we obtain a similar characterization for a cyclic Gray code faulting ▫$M$▫. In particular, in case that ▫$M$▫ is a perfect matching, ▫$Q_n$▫ has a (cyclic) Gray code faulting ▫$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.
    Vir: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 11, no. 2, 2009, str. 123-148)
    Vrsta gradiva - e-članek
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15521369

    Povezava(-e):

    http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1310

Vnos na polico