Generalized Nordhaus--Gaddum Inequalities for Eigenvalues

For a graph $G$, let ${\lambda }_1(G)\ge {\lambda }_2(G)\ge \cdots \ge {\lambda }_n(G)$ denote the adjacency eigenvalues of $G$. We investigate the asymptotic maximum of $${\lambda }_i(G)+{\lambda }_j(\bar{G})$$ for fixed $i$ and $j$. We prove general bounds on ${\lambda }_i(G)+{\lambda }_j(\bar{G})$ for all pairs $(i,j)$ and also give general bounds on the related problem of minimizing ${\lambda }_{n-i+1}(G)+{\lambda }_{n-j+1}(\bar{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, $${\lambda }_1(G)+{\lambda }_2(\bar{G})\le \frac{8}{7}n\mathrm{.}$$ Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that ${\lambda }_1(G)+{\lambda }_1(\bar{G})\le \frac{4}{3}n-1$. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.