Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

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 consider the question in hypercubes with faulty edges. We show for n >= 2 that every matching M of at most 2n - 1 edges extends to a Hamiltonian cycle in Q(n). Moreover, we prove that when n >= 4 and M is nonempty this conclusion still holds even if Q(n) has at most n - 1 - inverted right perpendicular vertical bar M vertical bar/2inverted left perpendicular faulty edges, with one exception. (C) 2014 Elsevier B.V. All rights reserved.