A NOTE ON LAPLACIAN GRAPH EIGENVALUES

Let G = (V, E) be a graph on n vertices. Denote by d(v) the degree of v is an element of V and by m(v) the average of the degrees of the ver tices of G adjacent to v. Then b(G) = max(m(v) + d(v): v is an element of V) is an upper bound for the Laplacian spectral radius of G; hence , n - b(G(C)) is a lower bound for the algebraic connectivity of G in terms of the vertex degrees of its complement. (C) 1998 Elsevier Scien ce Inc. All rights reserved.