LOCAL AND GLOBAL AVERAGE DEGREE IN GRAPHS AND MULTIGRAPHS

A vertex upsilon of a graph G is called groupie if the average degree t(upsilon) of all neighbors of upsilon in G is not smaller than the av erage degree t(G) of G. Every graph contains a groupie vertex; the pro blem of whether or not every simple graph on greater-than-or-equal-to2 vertices has at least two groupie vertices turned out to be surprisin gly difficult. We present various sufficient conditions for a simple g raph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min(upsilon)(t(upsilon)/t(G)), where the maxi mum ranges over all simple graphs on n vertices, and prove that f(n) = 1/4square-root2n + 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(upsilon) is constant. (C) 1994 John Wiley & Sons, Inc.