Gray Codes Avoiding Matchings
Gray Codes Avoiding Matchings
复制标题
DOI：
10.46298/dmtcs.457
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
D. Dimitrov;Tomáš Dvořák;Petr Gregor;R. Škrekovski
中科院分区：
文献类型：
--
作者：
D. Dimitrov;Tomáš Dvořák;Petr Gregor;R. Škrekovski
（循环）n位格雷码是长度为n的所有2n个二进制串的（循环）排序，使得连续串在单个位上不同。等价地，一个n比特格雷码可以看作是n维超立方体Qn的一条哈密尔顿路径，而一个循环格雷码可以看作是Qn的一个哈密尔顿圈.在本文中，我们研究（循环）格雷码避免了一组给定的故障边缘，形成一个匹配。给定一个匹配M和Qn，n≥4的两个顶点u，v，我们的主要结果给出了一个用M的禁用配置表示的充分必要条件，证明了u和v之间存在一个避开M的格雷码.作为推论，我们得到了一个类似的特征循环格雷码避免M。特别地，在M是完美匹配的情况下，Q n具有避免M的（循环）格雷码当且仅当Q n-M是连通图。这补充了Fink最近的一个结果，他证明了Q n的每一个完美匹配都可以扩展到一个Hamilton循环。此外，我们的研究结果意味着问题的哈密顿Q n故障边缘，这是NP-完全的一般，成为多项式为2 n-1的边缘，只要他们形成一个匹配。
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 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.