Hamiltonian decomposition of prisms over cubic graphs

Abstract : The prisms over cubic graphs are 4-regular graphs. The prisms over 3-connected cubic graphs are Hamiltonian. In 1986 Brian Alspach and Moshe Rosenfeld conjectured that these prisms are Hamiltonian decomposable. In this paper we present a short survey of the status of this conjecture, various constructions proving that certain families of prisms over 3-connected cubic graphs are Hamiltonian decomposable. Among others, we prove that the prisms over cubic Halin graphs, cubic generalized Halin graphs of order 4k + 2 and other infinite sequences of cubic graphs are Hamiltonian decomposable.
Keywords : Graph theory
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 16 no. 2 (in progress) (2), pp.111--124
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01185619
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 17:14:06
Dernière modification le : jeudi 7 septembre 2017 - 01:03:42
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:05:08

Fichier

dmtcs-16-2-9.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185619, version 1

Collections

Citation

Moshe Rosenfeld, Ziqing Xiang. Hamiltonian decomposition of prisms over cubic graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 16 no. 2 (in progress) (2), pp.111--124. 〈hal-01185619〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

231