Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and in edges and let mu(G) = mu(1) (G) >= (.) (.) (.) >= mu(n) (G) be the eigenvalues of its adjacency matrix. Set s(G) = Sigma(u is an element of V(G)) vertical bar d(u) - 2m/N vertical bar. We prove that s(2)(G)/2n(2)root 2m <= mu (G) - 2m/n <= root s(G). In addition we derive similar inequalities for bipartite G. We also prove that the inequality mu k(G) + mu(n-k+2)((G) over bar) >= -1-2 root 2s(G) holds for every k = 2..... n. Finally we prove that for every graph G of order n, mu(n) (G) + mu(n) ((G) over bar) <= -1- s(2)(G)/ 2n(3.) We show that these inequalities are tight up to a constant factor. (c) 2005 Elsevier Inc. All rights reserved.