Department of
Applied
Mathematics

Hamiltonian cycles in prisms over graphs

Moshe Rosenfeld

Abstract

The prism over a graph G is the Cartesian product G\Box K₂. My interest in prisms began in 1973 when I tried to tackle Dave Barnette's conjecture that all simple 4-polytopes are Hamiltonian (still open). Subsequently, we merged the study of Hamiltonian cycles in prisms with other refinements of Hamiltonian cycles. We observed that if G has a Hamiltonian prism then G has a spanning closed 2-walk but the opposite is not true, that is having a Hamiltonian prism is "closer" to being Hamiltonian than having a spanning, closed 2-walk. This observation created many opportunities to study various classical problems on Hamiltonicity of graphs. Two of the outstanding open problems are:

1. Is the prism over a 3-polytope (3-connected planar graph) Hamiltonian?
2. Do the prisms over 3-connected cubic graphs admit a Hamiltonian decomposition?

These problems are now part of Bondy and Murty's