Two Types of Matchings Extend to Hamiltonian Cycles in Hypercubes

Abstract

Ruskey and Savage posed the question: For $n\ge 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 that for $n\ge 3$, 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 $i$th position. We also show that for $n\ge 2$, every matching in $Q_n$ consisting of edges in at most four types extends to a Hamiltonian cycle in $Q_n$.