Hamiltonian decomposition of prisms over cubic graphs
Moshe Rosenfeld, Ziqing Xiang
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.
Full Text: PDF