On the Strongest Form of a Theorem of Whitney for Hamiltonian Cycles in Plane Triangulations. Issue 1 (28th August 2015)

• Record Type: Journal Article
• Authors: Brinkmann, Gunnar; Souffriau, Jasper; Van Cleemput, Nico
• Is Part Of: Journal of graph theory. Volume 83:Issue 1(2016)
• Page Start: 78
• Page End: 91
• Publication Date: 2015-08-28
• Subjects: hamiltonian cycle -- plane triangulation -- maximal planar graph -- decomposition tree; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21915
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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.