On Hamilton cycles in certain planar graphs.

*(English)*Zbl 0839.05068The 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.

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.

Reviewer: G.Schaar (Freiberg)

##### MSC:

05C45 | Eulerian and Hamiltonian graphs |

05C38 | Paths and cycles |

05C10 | Planar graphs; geometric and topological aspects of graph theory |