Premium
Hamilton cycles in plane triangulations
Author(s) -
Jackson Bill,
Yu Xingxing
Publication year - 2002
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.10057
Subject(s) - combinatorics , mathematics , planar graph , hamiltonian path , planar , plane (geometry) , triangulation , dual graph , hamiltonian (control theory) , graph , discrete mathematics , geometry , computer science , mathematical optimization , computer graphics (images)
We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002