Linear combinations of graph eigenvalues

Nikiforov, Vladimir

The electronic journal of linear algebra, Tome 15 (2006), pp. 329-336.

Résumé

Summary: Let $\mu_1(G)\ge\dots\ge \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\le i\le 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\le \max_{v(G)=n} \mu_1(G)+ \mu_2(G)\le \frac{2}{\sqrt{3}}n.$$ This inequality answers in the negative a question of Gernert.

Détail

Classification : 15A42, 05C50
Keywords: extremal graph eigenvalues, linear combination of eigenvalues, multiplicative property