Premium
On the Strongest Form of a Theorem of Whitney for Hamiltonian Cycles in Plane Triangulations
Author(s) -
Brinkmann Gunnar,
Souffriau Jasper,
Cleemput Nico
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21915
Subject(s) - mathematics , combinatorics , decomposition theorem , vertex (graph theory) , spanning tree , hamiltonian (control theory) , hamiltonian path , triangulation , decomposition , discrete mathematics , geometry , graph , mathematical optimization , ecology , biology
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, 4 or K 1, 5 . We also give computational results on the size of a possible minimal nonhamiltonian triangulation with these decomposition trees.