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.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI Link EuDML arXiv