×

Extending perfect matchings to Gray codes with prescribed ends. (English) Zbl 1391.05145

Summary: A binary (cyclic) Gray code is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the \(n\)-dimensional hypercube \(Q_n\) can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the “path version” of this problem. Namely, we characterize when a perfect matching in \(Q_n\) extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in \(Q_n\) with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions \(n\geq 5\) the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras’ conjecture with an additional edge, or with two faulty vertices. The proof for the case \(n=5\) is computer-assisted.

MSC:

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05A15 Exact enumeration problems, generating functions
94B25 Combinatorial codes
PDFBibTeX XMLCite
Full Text: Link

References:

[1] A. Alahmadi, R.E.L. Aldred, A. Alkenani, R. Hijazi, P. Sol´e, C. Thomassen, Extending a perfect matching to a Hamiltonian cycle, Discrete Math. Theor. Comput. Sci. 17 (2015), 241-254. the electronic journal of combinatorics 25(2) (2018), #P2.56 14 · Zbl 1311.05157
[2] D. Dimitrov, T. Dvoˇr´ak, P. Gregor, R. ˇSkrekovski, Gray codes avoiding matchings, Discrete Math. Theor. Comput. Sci. 11 (2009), 123-147. · Zbl 1192.94070
[3] T. Dvoˇr´ak, Matchings of quadratic size extend to long cycles in hypercubes, Discrete Math. Theor. Comput. Sci. 18 (2016), #12. · Zbl 1400.05129
[4] T. Dvoˇr´ak, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Dis crete Math. 19 (2005), 135-144. · Zbl 1082.05056
[5] T. Dvoˇr´ak, P. Gregor, Hamiltonian paths with prescribed edges in hypercubes, Discrete Math. 307 (2007), 1982-1998. · Zbl 1119.05060
[6] T. Dvoˇr´ak, P. Gregor, Hamiltonian fault-tolerance of hypercubes, in Proc. Eu ropean Conference on Combinatorics, Graph Theory and Applications (EuroComb 2007), Electron. Notes in Discrete Math. 29 (2007), 471-477. · Zbl 1341.05142
[7] T. Dvoˇr´ak, J. Fink, Gray codes extending quadratic matchings, J. Graph Theory (2018).doi:10.1002/jgt.22371. · Zbl 1466.05178
[8] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. The ory Ser. B 97 (2007), 1074-1076. · Zbl 1126.05080
[9] J. Fink, Matchings extend into 2-factors in hypercubes, Combinatorica (2018). doi:10.1007/s00493-017-3731-8. · Zbl 07058286
[10] F. Gray, Pulse Code Communication, U.S. Patent 2,632,058, filed 13 November 1947, issued 17 March 1953.
[11] L. A. Gross, Theorie du Baguenaudier, Aim´e Vingtrinier, Lyon, 1872.
[12] D. Knuth, The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011. · Zbl 1354.68001
[13] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Com bin. Appl. 16 (1996), 87-91. · Zbl 0855.05089
[14] T. M¨utze, Proof of the middle levels conjecture, Proc. Lond. Math. Soc. 112 (2016), 677-713. · Zbl 1336.05082
[15] T. Novotn´y,https://github.com/novotnyt94/Hypothesis-checker, 2017.
[16] F. Ruskey, C. D. Savage, Hamilton cycles that extend transposition matchings in Cayley graphs of S n, SIAM J. Discrete Math. 6 (1993), 152-166. · Zbl 0771.05050
[17] C. Savage, A survey of combinatorial Gray codes, SIAM Rev. 39 (1997), 605-629. · Zbl 1049.94513
[18] J. Vandenbussche, D. B. West, Matching extendibility in hypercubes, SIAM J. Discrete Math. 23 (2009), 1539-1547. · Zbl 1207.05161
[19] F. Wang, H. Zhang, Prescribed matchings extend to Hamiltonian cycles in hyper cubes with faulty edges, Discrete Math. 321 (2014), 35-44. · Zbl 1281.05100
[20] E. Zulkoski, C. Bright, A. Heinle, I. Kotsireas, K. Czarnecki, and V. Ganesh, Combining SAT Solvers with Computer Algebra Systems to Verify Combi natorial Conjectures, J. Autom. Reasoning 58 (2017), 313-339. · Zbl 1410.68413
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.