Kinds of Matchings Extending to Hamiltonian Cycles in Hypercube Networks

The hypercube Qn is a well-known and efficient interconnection network. Ruskey and Savage posed the following question: does every matching in a hypercube Qn for n≥2 extend to a Hamiltonian cycle? Fink addressed this by proving that every perfect matching extends to a Hamiltonian cycle in Qn, thereby resolving Kreweras’ conjecture. Ruskey and Savage’s problem is still open and has been proven only for small matchings. An edge of Qn is an i-edge when the binary representations of its endpoints differ at the ith coordinate. In this paper, we consider Qn for n≥3 and show that any matching consisting of edges of at most six types, which does not cover every pair of vertices at a distance of 3, extends to a Hamiltonian cycle.