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 tG, 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 tv, is defined as the arithmetic mean of the degrees of its neighbors. A vertex v of a graph G is called a groupie if tv \geq tG. 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 P4-free graphs. They also study the function f(n) = maxmaxv in G(tv/ tG), 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 tv 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