Authors: Adel Alahmadi ¹; Robert E. L. Aldred ²; Ahmad Alkenani ¹; Rola Hijazi ¹; P. Solé ^3,4; Carsten Thomassen ^5,1

• 1 Department of Mathematics [Jeddah]
• 2 Department of Mathematics and Statistics [Dunedin]
• 3 Department of Mathematics [Jeddah]
• 4 Télécom ParisTech
• 5 Department of Applied Mathematics and Computer Science [Lyngby]

Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d ≥7 and every k, where 7 ≤k ≤d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle. We do not know if this result can be extended to k=4,5,6. It cannot be extended to k=3. Indeed, there are only three 3-regular graphs such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle, namely the complete graph on 4 vertices, the complete bipartite 3-regular graph on 6 vertices and the 3-cube on 8 vertices. Also, we do not know if there are graphs of girth at least 5 with this matching-extendability property.

• 05C05 - Trees
• 60J80 - Branching processes (Galton-Watson, birth-and-death, etc.)

• 1 zbMATH Open