Extending a perfect matching to a Hamiltonian cycle

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.
Keywords : Hamiltonian cycle
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.241--254
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196849
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:09
Dernière modification le : vendredi 17 novembre 2017 - 13:10:01
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:09:08

Fichier

dmtcs-17-1-16.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196849, version 1

Collections

Citation

Adel Alahmadi, Robert E. L. Aldred, Ahmad Alkenani, Rola Hijazi, P. Solé, et al.. Extending a perfect matching to a Hamiltonian cycle. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.241--254. 〈hal-01196849〉

Partager

Métriques

Consultations de la notice

80

Téléchargements de fichiers

233