Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 07.05.2014 at 12:20 in S8, there is the following noon lecture:

Hamiltonian cycles in prisms over graphs

Moshe Rosenfeld

Abstract

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:

  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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010