# zbMATH — the first resource for mathematics

Linear combinations of graph eigenvalues. (English) Zbl 1142.05343
Summary: Let $$\mu_1(G)\geq\dots\geq \mu_n(G)$$ be the eigenvalues of the adjacency matrix of a graph $$G$$ of order $$n$$, and $$\overline{G}$$ be the complement of $$G$$. Suppose $$F(G)$$ is a fixed linear combination of $$\mu_i(G)$$, $$\mu_{n-i+1}(G)$$, $$\mu_i(\overline{G})$$, and $$\mu_{n-i+1}(\overline{G})$$, $$1\leq i\leq k$$. It is shown that the limit
$\lim_{n\to\infty} \tfrac1n\max \{F(G): v(G)=n\}$
always exists. Moreover, the statement remains true if the maximum is taken over some restricted families like “$$K_r$$-free” or “$$r$$-partite” graphs. It is also shown that
$\frac{29+\sqrt{329}}{42} n-25\leq \max_{v(G)=n} \mu_1(G)+ \mu_2(G)\leq \frac{2}{\sqrt{3}}n.$
This inequality answers in the negative a question of Gernert.

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 15A18 Eigenvalues, singular values, and eigenvectors
Full Text: