Extending matchings to Hamilton cycles in Hypercubes

Abstract

The main goal of this work is to study the problem of extending matchings to Hamilton cycles in hypercubes, a fundamental question in graph theory. We focus on the Ruskey--Savage conjecture, which states that every matching in the hypercube $Q_n$ can be extended to a Hamilton cycle. In particular, we formulate and prove some partial results of this conjecture, such as the validity of the conjecture for perfect matchings, known as Kreweras conjecture, and for small matchings, a result by Dvo\v{r}\'ak and Fink. In conclusion, we overview in depth and evaluate the existing progress on the Ruskey--Savage conjecture.