Hamiltonian decompositions of prisms over cubic graphs Original Research Article

A conjecture of Alspach and Rosenfeld states that the prism G □ K2 over any 3-connected cubic graph G has a decomposition into two Hamilton cycles. Using a method based on colored diagrams, we show this conjecture to hold for 3-connected planar bipartite cubic graphs and for one other class of planar cubic graphs known as ‘kleetope duals’. We also give a new proof of the fact that G □ K2 is hamiltonian for any 3-connected cubic graph G.