login/create account
Conjecture If 
is a 
-connected planar graph, then 
has a Hamilton cycle.
is a -connected planar graph, then has a Hamilton cycle. The Cartesian product is called the prism over .
Rosenfeld and Barnette [RB] showed that the Four-Colour Theorem implies that cubic planar 3-connected graphs have hamiltonian prisms. Fleischner [F] found a proof avoiding the use of the Four Colour Theorem. Eventually, Paulraja [P] showed that planarity is inessential here : The prism over any 3-connected cubic graph has a Hamilton cycle.
Clearly, if is hamiltonian, then is also hamiltonian. A classical theorem of Tutte [T] states that all 4-connected planar graphs are hamiltonian. There are well-known examples of non-hamiltonian 3-connected planar graphs.
Bibliography
[F] H. Fleischner, The prism of a 2-connected, planar, cubic graph is hamiltonian (a proof independent of the four colour theorem), in Graph theory in memory of G. A. Dirac, Volume 41 of Ann. Discrete Math., 1989), 141–170.
*[KKRRV] T. Kaiser, D. Kráľ, M. Rosenfeld, Z. Ryjáček, H.-J. Voss, Hamilton cycles in prisms, Journal of graph theory 56 (2007), 249-269.
[P] P. Paulraja, “A characterization of hamiltonian prisms”, J. Graph Theory 17 (1993) 161–171.
[RB] M. Rosenfeld and D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5 (1973) 389–394.
[T] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University