|
Abstract |
The work on finding a hamiltonian cycle in 4-connected graphs can be traced back to the early proof attempts of the four color theorem. In 1880, Tait observed that every hamiltonian plane graph is four face colorable. In this failed attempt, Tait made a couple of assumptions; one of them is that every 3-connected cubic planar graph is hamiltonian. The first counterexample was published by Tutte in 1946. On the other hand, Whitney in 1931 proved that every 4-connected plane triangulation contains a Hamiltonian cycle. Whitney's theorem has been generalized to all 4-connected planar graphs by Tutte: every 4-connected planar graph contains a hamiltonian cycle.
Tutte's result has played a central role in the development of topologic graph theory and has been generalized to projective-planar graphs, Klein bottles, toroidal graphs, and graphs embedded on other surfaces. Starting with a conjecture of Moon and Morser on circumference of a planar graph, we will address the following four topics related to the Tutte Theorem.
冘 Long cycles in 3-connected planar graphs;
冘 Long cycles in 3-connected graphs with no K3,t-minors;
冘 Long cycles in 3-connected graphs with bounded degree; and
冘 Spanning trees without degree 2 vertices (HIST) in triangulations
of surfaces and their generalizations. |
