Authors: F. Wang, W. Zhao Title: Matchings extend to Hamiltonian cycles in 5-cube Source: Discussiones Mathematicae Graph Theory Received 27.09.2016, Revised 04.11.2016, Accepted 04.11.2016, doi: 10.7151/dmgt.2010 | |
Abstract: Ruskey and Savage asked the following question: Does every matching in a hypercube Q_{n} for n≥2 extend to a Hamiltonian cycle of Q_{n}? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Q_{n}, thus solved Kreweras' conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Q_{n} for n∈{2,3,4}. In this paper, we prove that every matching in Q_{5} can be extended to a Hamiltonian cycle of Q_{5}. | |
Keywords: hypercube, Hamiltonian cycle, matching | |
Links: |