Alahmadi, Adel; Aldred, Robert E. L.; Alkenani, Ahmad; Hijazi, Rola; SolĂ©, Patrick; Thomassen, Carsten Extending a perfect matching to a Hamiltonian cycle. (English) Zbl 1311.05157 Discrete Math. Theor. Comput. Sci. 17, No. 1, 241-254 (2015). Summary: F. Ruskey and C. Savage [SIAM J. Discrete Math. 6, No. 1, 152–166 (1993; Zbl 0771.05050)] conjectured that in the \(d\)-dimensional hypercube, every matching \(M\) can be extended to a Hamiltonian cycle. J. Fink [J. Comb. Theory, Ser. B 97, No. 6, 1074–1076 (2007; Zbl 1126.05080)] 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 \geq 7\) and every \(k\), where \(7 \leq k \leq 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. Cited in 2 ReviewsCited in 8 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C45 Eulerian and Hamiltonian graphs Keywords:well classifying words; matching-extendability property Citations:Zbl 0771.05050; Zbl 1126.05080 PDFBibTeX XMLCite \textit{A. Alahmadi} et al., Discrete Math. Theor. Comput. Sci. 17, No. 1, 241--254 (2015; Zbl 1311.05157) Full Text: Link