A kind of matchings extend to Hamiltonian cycles in hypercubes

Ruskey and Savage asked the following question: Does every matching in Q n for n ≥ 2 extend to a Hamiltonian cycle of Q n ? Kreweras conjectured that every perfect matching of Q n for n ≥ 2 can be extended to a Hamiltonian cycle of Q n . Fink confirmed the conjecture. An edge in Q n is an edge of direction i if its endpoints differ in the i th position. So all the edges of Q n 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 Q n is denoted by E i . In this paper, we obtain the following result. For n ≥ 6, let M be a matching in Q n with |M| < 10 × 2 n −5 . If M contains edges in at most 5 directions, then M can be extended to a Hamiltonian cycle of Q n .