5-CONNECTED TOROIDAL GRAPHS ARE HAMILTONIAN-CONNECTED

The problem on the Hamiltonicity of graphs is well studied in discrete algorithm and graph theory because of its relation to the traveling salesman problem. Starting with Tutte's result, stating that every 4-connected planar graph is Hamiltonian, several researchers have studied the Hamiltonicity of graphs on surfaces. Extending Tutte's technique, Thomassen proved that every 4-connected planar graph is in fact Hamiltonian-connected, i.e., there is a Hamiltonian path connecting any two prescribed vertices. For graphs on the torus, Thomas and Yu showed that every 5-connected graph on the torus has a Hamiltonian cycle. In this paper, we prove the following result which generalizes Thomas and Yu's result. Every 5-connected graph on the torus is Hamiltonian-connected. Our result is best possible in the sense that we cannot lower the connectivity 5 (i.e., there is a 4-connected graph on the torus which is not Hamiltonian-connected). Moreover, our proof is constructive in a sense that it gives rise to a polynomial time (indeed O(n(2))-time) algorithm to construct a Hamiltonian path between any two specified vertices, if an input graph is a 5-connected graph on the torus.