HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185619
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 5:14:06 PM
Last modification on : Wednesday, October 28, 2020 - 7:48:02 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:05:08 AM

File

dmtcs-16-2-9.pdf
Publisher files allowed on an open archive

Identifiers

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 (2), pp.111--124. ⟨10.46298/dmtcs.2079⟩. ⟨hal-01185619⟩

Share

Metrics

Record views

56

Files downloads

1110