More spectral bounds on the clique and independence numbers

We give some new bounds for the clique and independence numbers of a graph in terms of its eigenvalues. In particular we prove the following results. Let G be a graph of order n, average degree d, independence number alpha(G), and clique number omega(G). (i) If mu(n) is the smallest eigenvalue of G, then omega(G) >= 1 + dn/(n-d)(d-mu(n)) Equality holds if and only if G is a complete regular omega-partite graph. (ii) if (mu(n)) over bar is the smallest eigenvalue of the complement of G, and 2 <= d< n-1, then alpha(G) > (n/d + 1 - 1)(In d + 1 /-mu(n) - In In(d +1)). For d sufficiently large this inequality is tight up to factor of 4 for almost all d-regular graphs. (C) 2009 Elsevier Inc. All rights reserved.