×

zbMATH — the first resource for mathematics

More about the weight of edges in planar graphs. (English) Zbl 0854.05039
Define the weight of an edge of graph \(G\) to be the sum of the degrees of its vertices. Let \(w\) denote the minimum weight of edges in \(G\). Let \(w^*\) denote the minimum weight of edges that are incident with at least one triangle. Let \(w^{**}\) denote the minimum weight of edges that are incident with at least two triangles. Clearly, \(w\leq w^*\leq w^{**}\). The results of the paper apply to planar maps \(G\) in which every face and every vertex is incident with at least three edges. The paper shows that if \(w^{**}= \infty\), then either \(w^*\leq 9\) or \(w\leq 8\), and both bounds are sharp.
Reviewer: M.Marx (Pensacola)

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDF BibTeX Cite