Hamiltonian-connectedness of triangulations with few separating triangles

Keywords: triangulation, maximal planar graph, hamiltonian-connected, decomposition tree

Abstract

We prove that 3-connected plane triangulations containing a single edge contained in all separating triangles are hamiltonian-connected. As a direct corollary we have that 3-connected plane triangulations with at most one separating triangle are hamiltonian-connected. In order to show bounds on the strongest form of this theorem, we proved that for any s >= 4 there are 3-connected triangulation with s separating triangles that are not hamiltonian-connected. We also present computational results which show that all `small' 3-connected triangulations with at most 3 separating triangles are hamiltonian-connected.

References

T. Böhme, J. Harant, and M. Tkáč. On the minimal number of separating 3-cycles in non-Hamiltonian maximal planar graphs. Tatra Mt. Math. Publ. 9:97–102, 1996.

Gunnar Brinkmann, Jasper Souffriau, and Nico Van Cleemput. On the strongest form of a theorem of Whitney for hamiltonian cycles in plane triangulations. J. Graph Theory, 83(1):78–91, 2015.

George R.T. Hendry. Scattering number and extremal non-hamiltonian graphs. Discrete Mathematics, 71(2):p.165 – 175, 1988.

Bill Jackson and Xingxing Yu. Hamilton cycles in plane triangulations. Journal of Graph Theory, 41(2):p.
138–150, 2002.

Heinz A. Jung. On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory, Series B, 24(2):p. 125 – 133, 1978.

Kenta Ozeki and Petr Vrána. 2-edge-hamiltonian-connectedness of 4-connected plane graphs. European Journal of Combinatorics, 35:p. 432 – 448, 2014. Selected Papers of EuroComb’11.

Carsten Thomassen. A theorem on paths in planar graphs. Journal of Graph Theory, 7(2):p. 169–176, 1983.

Hassler Whitney. A theorem on graphs. The Annals of Mathematics, 32(2):p. 378 – 390, 1931.
Published
2019-12-25
Section
Articles