More eigenvalue problems of Nordhaus-Gaddum type

Abstract

Let $G$ be a graph of order $n$ and let ${\mu }_1\left(G\right)\ge \cdots \ge {\mu }_n\left(G\right)$ be the eigenvalues of its adjacency matrix. This note studies eigenvalue problems of Nordhaus-Gaddum type. Let $\overline{G}$ be the complement of a graph $G.$ It is shown that if $s\ge 2$ and $n\ge 15\left(s-1\right),$ then \[ \left\vert μ_{s}\left(G\right) \right\vert +|μ_{s}(\overline{G})|\,\leq n/\sqrt{2\left(s-1\right)}-1. \] Also if $s\ge 1$ and $n\ge 4^s,$ then \[ \left\vert μ_{n-s+1}\left(G\right) \right\vert +|μ_{n-s+1}(\overline {G})|\,\leq n/\sqrt{2s}+1. \] If $s=2^k+1$ for some integer $k$, these bounds are asymptotically tight. These results settle infinitely many cases of a general open problem.

12 pages, 0 figures