Extending a perfect matching to a Hamiltonian cycle
Adel Alahmadi, Robert E.L. Aldred, Ahmad Alkenani, Rola Hijazi, Patrick Solé, Carsten Thomassen
Abstract
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.
Full Text: PDF PostScript