Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

Ruskey and Savage asked the following question: for n≥2n≥2, does every matching in QnQn extend to a Hamiltonian cycle in QnQn? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras’ conjecture. In this paper we consider the question in hypercubes with faulty edges. We show for n≥2n≥2 that every matching MM of at most 2n−12n−1 edges extends to a Hamiltonian cycle in QnQn. Moreover, we prove that when n≥4n≥4 and MM is nonempty this conclusion still holds even if QnQn has at most n−1−⌈|M|2⌉ faulty edges, with one exception.