×

zbMATH — the first resource for mathematics

The weight of a graph. (English) Zbl 0773.05066
Combinatorics, graphs and complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math. 51, 113-116 (1992).
[For the entire collection see Zbl 0748.00023.]
The weight of an edge in a graph \(G\) is the sum of degrees of its end vertices. The weight of \(G\), \(w(G)\), is the minimum weight among all its edges. The author shows that for a graph with minimum degree at lest 3 and genus \(g\) it holds \(w(G)\leq 2g+13\) for \(0\leq g\leq 3\), otherwise \(w(G)\leq 4g+7\); and the bounds are best possible.

MSC:
05C35 Extremal problems in graph theory
Keywords:
weight; genus; bounds
PDF BibTeX XML Cite