Generalized Nordhaus--Gaddum Inequalities for Eigenvalues

Abstract

For a graph $G$, let $\hat{I}{»}_1(G)\ge \hat{I}{»}_2(G)\ge \cdots \ge \hat{I}{»}_n(G)$ denote the adjacency eigenvalues of $G$. We investigate the asymptotic maximum of \[ λ_i(G)+λ_j(\overline G) \] for fixed $i$ and $j$. We prove general bounds on $\hat{I}{»}_i(G)+\hat{I}{»}_j(\overline{G})$ for all pairs $(i,j)$ and also give general bounds on the related problem of minimizing $\hat{I}{»}_{n-i+1}(G)+\hat{I}{»}_{n-j+1}(\overline{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, \[λ_1(G) + λ_2(\overline{G}) \le \frac87 n. \] Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that $\hat{I}{»}_1(G)+\hat{I}{»}_1(\overline{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.

18 pages; comments welcome!