A kind of matchings extend to Hamiltonian cycles in hypercubes
Shujia Wang, Fan Wang · RAIRO - Operations Research · 2024
Ruskey and Savage asked the following question: Does every matching in Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Kreweras conjectured that every perfect matching of Qn for n ≥ 2 can be extended to a Hamiltonian cycle of Qn. Fink confirmed the conjecture. An edge in Qn is an edge of direction i if its endpoints differ in the ith position. So all the edges of Qn can be divided into n directions, i.e., edges of direction 1, …, edges of direction n. The set of all edges of direction i of Qn is denoted by Ei. In this paper, we obtain the following result. For n ≥ 6, let M be a matching in Qn with |M| < 10 × 2n−5. If M contains edges in at most 5 directions, then M can be extended to a Hamiltonian cycle of Qn.