An always nontrivial upper bound for Laplacian graph eigenvalues

Let G be a graph on vertex set V = {v(1), v(2),..., v(n)}. Let d(i) be the degree of v(i), let N-i be the set of neighbours of v(i) and let /S/ be the number of vertices of S subset of or equal to V: In this note, we prove th at max {d(i) + d(i) - /N-i boolean AND N-j/ : 1 less than or equal to i < j le ss than or equal to n} is an upper bound for the largest eigenvalue of the Laplacian matrix of G. For any G, this bound does not exceed the order of G. (C) 2000 Elsevier Sci ence Inc. All rights reserved. AMS classification: 05C50.