# zbMATH — the first resource for mathematics

On Hamilton cycles in certain planar graphs. (English) Zbl 0839.05068
The main result of this paper generalizes both the well-known theorem of Tutte that every 4-connected planar graph is Hamiltonian, as well as a theorem of M. B. Dillencourt [J. Graph Theory 14, No. 1, 31-49 (1990; Zbl 0688.05052)] that planar triangulations satisfying certain conditions are Hamiltonian, either theorem being a generalization of Whitney’s theorem on 4-connected planar triangulations. This result is formulated in two versions, the second reads as follows: Let $$G$$ be a (simple) 2-connected plane graph, $$C(G)$$ its outer cycle (= outer face, i.e. the face belonging to the unbounded region) satisfying that for every minimal vertex cut-set $$S$$ of $$G$$ with $$|S|\leq 3$$, every component of $$G- S$$ contains a vertex of $$C(G)$$. If each active face of $$BG(G)$$ contains at most three chords of $$BG(G)$$, then $$G$$ is Hamiltonian.
Here, a face of a plane graph $$H= (V(H), E(H))$$ is the subgraph forming the boundary of a region (of the complement of $$H$$ in the plane); a chord of $$H$$ is an edge joining two vertices $$u$$, $$v$$ of its outer face $$C(H)$$ with $$uv\not\in E(C(H))$$; a chordal face $$F$$ of $$H$$ is a face $$F\neq C(H)$$ that contains two different vertices $$u$$, $$v$$ of $$C(H)$$ with $$uv\not\in E(C(H))$$; two different vertices $$u$$, $$v$$ on $$C(H)$$ are admissible in $$H$$ iff there is a chordal face containing $$u$$ and $$v$$ and there is a path in $$H$$ joining $$u$$ and $$v$$ and containing no other vertices of $$C(H)$$ and no edges of $$C(H)$$. Now, for the graph $$G$$ mentioned above, its boundary graph $$BG(G)$$ is defined to have $$V(BG(G))= V(C(G))$$ and for $$u$$, $$v$$ on $$C(G)$$, $$u\neq v$$, $$uv\in E(BG(G))$$ iff either $$uv\in E(G)$$ or $$u$$, $$v$$ are admissible in $$G$$. A face $$F$$ of $$BG(G)$$ is said to be active iff there is at least one vertex of $$G$$ in its interior (i.e. in the bounded region with the boundary $$F$$).
The proof yields a linear algorithm for finding a Hamiltonian cycle. Furthermore, it follows that for a 4-connected planar graph $$G$$ and vertices $$x$$, $$y$$, $$z$$ spanning a triangle in $$G$$, the graph $$G- \{x, y, z\}$$ is Hamiltonian, too.

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: