Linear combinations of graph eigenvalues

Abstract

Let µ₁ (G) ≥ ... ≥ µ_n (G) be the eigenvalues of the adjacency matrix of a graph G
of order n, and Ḡ  be the complement of G. Suppose F (G) is a fixed linear combination of µ_i (G), µ_n−i+1 (G) , µ_i (Ḡ), and µ_n−i+1 (Ḡ), 1 ≤ i ≤ k. It is shown that the limit

lim _n→∞ 1/n max {F (G) : v (G) = n｝

always exists. Moreover, the statement remains true if the maximum is taken over some restricted families like “Kr-free” or “r-partite” graphs. It is also shown that

(29+√329/42)n-25 ≤ max_v(G)=n µ₁ (G) + µ₂ (G) ≤ (2/√3)n

This inequality answers in the negative a question of Gerne.