The hypercube Formula: see text is a well-known interconnection network topology due to its symmetry, regularity, and recursive structure. A longstanding open problem posed by Ruskey and Savage asks whether every matching in Formula: see text, for Formula: see text, can be extended to a Hamiltonian cycle. Despite over three decades, this problem remains unresolved. However, this conjecture holds for certain special classes of matchings, such as perfect matchings, linear matchings, and some kinds of matchings. It is important to note that not every matching in a hypercube can be extended to a perfect matching. In this study, we contribute to this problem by proving that any matching in the Formula: see text-dimensional hypercube Formula: see text with at most Formula: see text edges can be extended to a Hamiltonian cycle, for Formula: see text.
Ali et al. (Sat,) studied this question.