Eigenvalue problems of Nordhaus--Gaddum type (Q868345)

Consider a graph \(G\) with \(\nu(G)=n\) vertices. The eigenvalues of the adjacency matrix of \(G\) are arranged as \(\mu_1(G)\geq\cdots\geq\mu_n(G)\). Let \(\overline{G}\) denote the complement of \(G\). In this paper for \(k\) fixed and \(n\) large, estimates are derived for \[ f_k(n)=\max_{\nu(G)=n}| \mu_k(G)| +| \mu_k(\overline{G})| . \] It is shown that for some \(c>10^{-7}\) independent of \(n\) \[ \frac{4}{3}n-2\leq f_1(n)<(\sqrt{2}-c)n \] and \[ \frac{\sqrt{2}}{2}n-3<f_2(n)<\frac{\sqrt{2}}{2}n,\\ \frac{\sqrt{2}}{2}n-3<f_n(n)\leq\frac{\sqrt{3}}{2}n. \]