Cliques and the spectral radius

We prove a number of relations between the number of cliques of a graph G and the largest eigenvalue μ (G) of its adjacency matrix. In particular, writing ks (G) for the number of s-cliques of G, we show that, for all r ≥ 2,μr + 1 (G) ≤ (r + 1) kr + 1 (G) + underover(∑, s = 2, r) (s - 1) ks (G) μr + 1 - s (G), and, if G is of order n, thenkr + 1 (G) ≥ (frac(μ (G), n) - 1 + frac(1, r)) frac(r (r - 1), r + 1) (frac(n, r))r + 1 . © 2007 Elsevier Inc. All rights reserved