zbMATH — the first resource for mathematics

Short cycles of low weight in normal plane maps with minimum degree 5. (English) Zbl 0927.05069
The weight of a subgraph in a plane map \(M\) is the sum of the degrees (in \(M\)) of its vertices. \(w(S)\) denote the minimum weight of a subgraph isomorphic to \(S\) in \(M\). In the paper, precise upper bounds for weights of a 4-cycle and a 5-cycle in any plane triangulation with minimum degree 5 are determined. Namely, \(w(C_4) \leq 25\) and \(w(C_5) \leq 30\) because any normal plane map with minimum degree 5 must contain a 4-star with \(w(K_{1,2}) \leq 30\). These results answer a question posed by Kotzig in 1979 and questions of S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207-217 (1996; Zbl 0877.05050)].

05C75 Structural characterization of families of graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI Link