An improved upper bound for Laplacian graph eigenvalues

Let G = (V, E) be a simple graph on vertex set V = {nu(1), nu(2),...., nu(n)}. Further let d(i) be the degree of nu(i) and N-i be the set of neighbors of nu(i). It is shown that max {d(i) + d(j) - \N-i boolean AND N-j\ : 1 less than or equal to i < i less than or equal to n, nu(i)nu(j) is an element of E} is an upper bound for the largest eigenvalue of the Laplacian matrix of G, where \N-i boolean AND N-j\ denotes the number of common neighbors between nu(i) and nu(j). For any G, this bound does not exceed the order of G. Further using the concept of common neighbors another upper bound for the largest eigenvalue of the Laplacian matrix of a graph has been obtained as max {root2(d(i)(2) + d(i)m(i)') : 1 less than or equal to i less than or equal to n}, where m(i)' = Sigma(j) {d(j) - \N-i boolean AND N-j\ : nu(i) nu(j) E/d(i)}. (C) 2003 Elsevier Science Inc. All rights reserved.