Home » Subject » Graph Theory » Topological G.T.

Every 4-connected toroidal graph has a Hamilton cycle

Importance: Medium ✭✭
Author(s): Grunbaum, Branko
Nash-Williams, Crispin, St. J. A.
Subject: Graph Theory
» Topological Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 7th, 2013
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.
add new comment