Eigenvalues and extremal degrees of graphs

Let G be a graph with n vertices, μ1 (G) ≥ ⋯ ≥ μn (G) be the eigenvalues of its adjacency matrix, and 0 = λ1 (G) ≤ ⋯ ≤ λn (G) be the eigenvalues of its Laplacian. We show thatδ (G) ≤ μk (G) + λk (G) ≤ Δ (G) for all 1 ≤ k ≤ nandμk (G) + μn - k + 2 (over(G, -)) ≥ δ (G) - Δ (G) - 1 for all 2 ≤ k ≤ n . Let G be an infinite family of graphs. We prove that G is quasi-random if and only if μn (G) + μn (over(G, -)) = o (n) for every G ∈ G of order n. This also implies that if λn (G) + λn (over(G, -)) = n + o (n) (or equivalently λ2 (G) + λ2 (over(G, -)) = o (n)) for every G ∈ G of order n, then G is quasi-random. © 2006 Elsevier Inc. All rights reserved