##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 812.05032

**Autor: ** Bertram, E.; Erdös, Paul; Horák, P.; Sirán, J.; Tuza, Zs.

**Title: ** Local and global average degree in graphs and multigraphs. (In English)

**Source: ** J. Graph Theory 18, No.7, 647-661 (1994).

**Review: ** The global average degree of a graph G, denoted by t_{G}, is defined as the arithmetic mean of the degrees of all vertices of G. For a vertex v in G, the local average degree of v, denoted by t_{v}, is defined as the arithmetic mean of the degrees of its neighbors. A vertex v of a graph G is called a groupie if t_{v} \geq t_{G}. It was conjectured by the authors that every simple graph with at least two vertices contains at least two groupie vertices. In this paper, the authors show that this conjecture holds for several special families of graphs, such as biregular graphs and P_{4}-free graphs. They also study the function f(n) = **max****max**_{v in G}(t_{v}/ t_{G}), where the maximum is taken over all graphs G on n vertices, and prove that f(n) = ^{1}/_{4} \sqrt {2n}+O(1). The corresponding result for multigraphs is discussed. The authors also characterize the trees in which the local average degree t_{v} is constant.

**Reviewer: ** Z.Chen (Indianapolis)

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** global average degree; groupie; groupie vertices; trees; local average degree

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag