Short cycles of low weight in normal plane maps with minimum degree 5. (English) Zbl 0927.05069

Borodin, Oleg V.; Woodall, Douglas R.

Discuss. Math., Graph Theory 18, No. 2, 159-164 (1998).

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

Reviewer: Stanislav Jendrol’ (Košice)

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