×

zbMATH — the first resource for mathematics

Hamilton cycles in plane triangulations. (English) Zbl 1012.05106
Summary: 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.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cunningham, Can J Math 32 pp 734– (1980) · Zbl 0442.05054 · doi:10.4153/CJM-1980-057-7
[2] Dillencourt, J Graph Theory 14 pp 31– (1990)
[3] Thomas, J Combin Theory Ser B 62 pp 114– (1994)
[4] Thomassen, J Graph Theory 7 pp 169– (1983)
[5] Tutte, Trans Am Math Soc 82 pp 99– (1956)
[6] Whitney, Ann Math 32 pp 378– (1931)
[7] Yu, Trans Am Math Soc 349 pp 1333– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.