Abstract

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 that max {d(i) + d(i) - /N-i boolean AND N-j/ : 1 less than or equal to i < j less 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 Science Inc. All rights reserved. AMS classification: 05C50.