-
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.Source: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 11, no. 2, 2009, str. 123-148)Type of material - e-articlePublish date - 2009Language - englishCOBISS.SI-ID - 15521369
Author
Dimitrov, Darko |
Dvořák, Tomáš, matematik |
Gregor, Petr |
Škrekovski, Riste
Topics
matematika |
teorija grafov |
Grayjeva koda |
hiper kocka |
Hamiltonova pot |
Hamiltonov cikel |
mathematics |
graph theory |
hipercube |
Gray code |
Hamiltonian path |
Hamiltonian cycle |
matching |
fault tolerance
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dimitrov, Darko | 50728 |
Dvořák, Tomáš, matematik | ![]() |
Gregor, Petr | 38085 |
Škrekovski, Riste | 15518 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.