Eigenvalue problems of Nordhaus-Gaddum type

Let G be a graph with n vertices and in edges and let mu(1) (G) >= ... >= (G) be the eigenvalues of its adjacency matrix. We discuss the following general problem. For k fixed and n large, find or estimate f(k)(n) = max(nu(G)=n)vertical bar mu(k)(G)vertical bar+vertical bar mu(k)((G) over bar) In particular, we prove that (4)/(3)n - 2 <= f(1) (n) < (root 2 - c)n for some c > 10(-7) independent of n. We also show that (root 2)/(2)n - 3 < f(2)(n) < (root 2)/(2) n, (root 2)/(2)n - 3 < f(2)(n) < (root 3)/(2) n, (c) 2006 Elsevier B.V. All rights reserved.