login/create account
Conjecture Every 4-connected toroidal graph has a Hamilton cycle.
Tutte [Tu] proved that every 4-connected planar graph has a Hamilton cycle. (See also [Th]). Thomas and Yu [TY] proved that every 4-connected projective-planar graph has a Hamilton cycle.
Thomas and Yu [TY] also proved that every 5-connected toroidal graph has a Hamilton cycle. In fact, they show something stronger: every edge in a 5-connected toroidal graph is contained in a Hamilton cycle. This stronger result cannot be extended to 4-connected toroidal graphs: Thomassen [Th] showed 4-connected toroidal graphs in which certain edges are not contained in any Hamilton cycle.
Bibliography
*[G] B. Grünbaum, Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76 (1970) 1131-1201.
*[N] C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory. New Directions in Graph Theory, Academic Press, New York (1973) 169-176.
[TY] R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B 69 (1997), no.1, 79-96.
[Th] C. Thomassen, A theorem on paths in planar graphs. J. Graph Theory 7 (1983) 169-176.
[Tu] 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