More eigenvalue problems of Nordhaus-Gaddum type

Let $G$ be a graph of order $n$ and let $μ_{1}\left(G\right) \geq \cdots\geqμ_{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\geq2$ and $n\geq15\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\geq1$ and $n\geq4^{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.

No reviews yet.

No comments yet.