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.,
Send comments to dan.archdeacon@uvm.edu
December 2003