zbMATH — the first resource for mathematics

The 10-cycle \(C_{10}\) is light in the family of all plane triangulations with minimum degree five. (English) Zbl 0951.05031
A subgraph of a plane graph is light if each of its vertices has a small degree in the entire graph. Consider the class \(\mathcal T(5)\) of all plane triangulations of minimum degree 5. It is known that each \(G\in \mathcal T(5)\) contains a light triangle, see, e.g., O. V. Borodin [Solution of Kotzig-Grünbaum problems on separation of a cycle in planar graphs, Mat. Zametki 46, No. 5, 9-12 (1989; Zbl 0694.05027)]. From a recent result of S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207-217 (1996; Zbl 0877.05050)], the existence of light cycles \(C_4\) and \(C_5\) in each \(G\in \mathcal T(5)\) follows. S. Jendrol’, T. Madaras, R. Soták and Zs. Tuza [Discrete Math. 197-198, 453-467 (1999; Zbl 0936.05065)] proved that each \(G\in \mathcal T(5)\) contains light cycles \(C_6, C_7, C_8\) and \(C_9\), and that no cycle \(C_k\) with \(k\geq 11\) is light in the class \(\mathcal T(5)\). In this paper the authors supplement the above-mentioned results by proving that each \(G\in \mathcal T(5)\) also contains a light cycle \(C_{10}\) such that every of its vertices is of degree at most 415. So the characterization of all light cycles in \(\mathcal T(5)\) is complete.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
52B10 Three-dimensional polytopes