# 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)].

##### MSC:
 05C75 Structural characterization of families of graphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
##### Keywords:
planar graphs; plane triangulation; light subgraphs; weight
Full Text: