Two types of matchings extend to Hamiltonian cycles in hypercubes.
Fan Wang, Heping Zhang · Lanzhou University Institutional Repository · 2015
Ruskey and Savage asked the following question: For n >= 2, does every matching in Q(n) extend to a Hamiltonian cycle in Q(n)? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras' conjecture. In this paper, we prove for n >= 3 that every matching in Q(n) not covering exactly two vertices at distance 3 extends to a Hamiltonian cycle in Q(n). An edge in Q(n) is an i-edge if its endpoints differ in the ith position. We show for n >= 2 that every matching in Q(n) consisting of edges in at most four types extends to a Hamiltonian cycle in Q(n).