Local and global average degree in graphs and multigraphs

A vertex v of a graph G is called groupie if the average degree t v of all neighbors of v in G is not smaller than the average degree t G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f ( n ) = max min v ( t v / t G ), where the maximum ranges over all simple graphs on n vertices, and prove that f ( n ) = 1/42 n + o (1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t v is constant.