Alahmadi, Adel and Aldred, Robert E. L. and Alkenani, Ahmad and Hijazi, Rola and Solé, P.et al. - Extending a perfect matching to a Hamiltonian cycle

dmtcs:2105 - Discrete Mathematics & Theoretical Computer Science, March 28, 2015, Vol. 17 no. 1 (in progress)
Extending a perfect matching to a Hamiltonian cycle

Authors: Alahmadi, Adel and Aldred, Robert E. L. and Alkenani, Ahmad and Hijazi, Rola and Solé, P. and Thomassen, Carsten

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.


Source : oai:HAL:hal-01196849v1
Volume: Vol. 17 no. 1 (in progress)
Section: Graph Theory
Published on: March 28, 2015
Submitted on: May 21, 2014
Keywords: Hamiltonian cycle,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]


Share

Browsing statistics

This page has been seen 45 times.
This article's PDF has been downloaded 31 times.