Hamilton Cycles in Toroidal graphs



Tutte [T] proved that every 4-connected toroidal graph has a Hamiltonian cycle. He conjectured::

Conjecture: Every 4-connected toroidal graph is Hamiltonian

I have also heard that this was independently conjectured by Grunbaum. Thomas and Xu [TX] have shown that 5-connected toroidal graphs are Hamiltonian.

A polyhedron P of genus g is formed by identifying polyhedra face-to-face so that the resulting surface is of genus g. There are toroidal graphs that cannot be realized as toroidal polyhedra [X].
Hence the following is strictly weaker than Conjecture 1.

Conjecture 2: Every 4-connected toroidal polyhedron is Hamiltonian.

References:

[D] N. Dean, Open problems, Contemporary Mathematics 147 (1993) 677-688

[TY] R. Thomas, X. Yu, Five-connected toroidal graphs are Hamiltonian,  J. Combin. Theory Ser. B 69-1 (1997) 79--96

[T] W.T. Tutte, A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956), 99--116.

[X] N.H. Xuong, Sur quelques problems d'immersion d'un graphs dans une surface, These de Doctorat d'Etat, Grenoble (1977)


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003