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 Qn for n≥2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras' conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n∈{2,3,4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
Keywords:
hypercube, Hamiltonian cycle, matching

Links:
PDF