On the Strongest Form of a Theorem of Whitney for Hamiltonian Cycles in Plane Triangulations

摘要

In this article, we investigate hamiltonian cycles in plane triangulations. The aim of the article is to find the strongest possible form of Whitney's theorem about hamiltonian triangulations in terms of the decomposition tree defined by separating triangles. We will decide on the existence of nonhamiltonian triangulations with given decomposition trees for all trees except trees with exactly one vertex with degree k{4,5} and all other degrees at most 3. For these cases, we show that it is sufficient to decide on the existence of nonhamiltonian triangulations with decomposition tree K-1,K- 4 or K-1,K- 5. We also give computational results on the size of a possible minimal nonhamiltonian triangulation with these decomposition trees.