{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T03:16:28Z","timestamp":1778555788054,"version":"3.51.4"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Graph and Algorithms","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Graphs and Algorithms<\/jats:p>\n          <jats:p xml:lang=\"en\">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 &gt;= 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.<\/jats:p>","DOI":"10.46298\/dmtcs.457","type":"journal-article","created":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T21:45:13Z","timestamp":1629755113000},"source":"Crossref","is-referenced-by-count":3,"title":["Gray codes avoiding matchings"],"prefix":"10.46298","volume":"Vol. 11 no. 2","author":[{"given":"Darko","family":"Dimitrov","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik [Berlin]"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-5853-4254","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Dvo\u0159\u00e1k","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Physics [Praha\/Prague]"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-3608-2533","authenticated-orcid":false,"given":"Petr","family":"Gregor","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Physics [Praha\/Prague]"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-6851-3214","authenticated-orcid":false,"given":"Riste","family":"\u0160krekovski","sequence":"additional","affiliation":[{"name":"Oddelek za Matematiko"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2009,1,1]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/457\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/457\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T19:55:46Z","timestamp":1687290946000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,1]]},"references-count":0,"journal-issue":{"issue":"Graph and Algorithms","published-online":{"date-parts":[[2009,1,1]]}},"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.46298\/dmtcs.457","relation":{"is-same-as":[{"id-type":"uri","id":"https:\/\/2.zoppoz.workers.dev:443\/https\/hal.science\/hal-00988206v1","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"value":"1365-8050","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,1]]},"article-number":"457"}}