On 07.05.2014 at 12:20 in S8, there is the following noon lecture:
Hamiltonian cycles in prisms over graphs
The prism over a graph G is the Cartesian product G\Box K2. 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:
- Is the prism over a 3-polytope (3-connected planar graph) Hamiltonian?
- Do the prisms over 3-connected cubic graphs admit a Hamiltonian decomposition?
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010