pith. sign in

arxiv: 1401.4365 · v2 · pith:J72NX7EZnew · submitted 2014-01-07 · 🧮 math.CO

More eigenvalue problems of Nordhaus-Gaddum type

classification 🧮 math.CO
keywords leftrightvertoverlineeigenvaluegraphnordhaus-gaddumproblems
0
0 comments X
read the original abstract

Let $G$ be a graph of order $n$ and let $\mu_{1}\left(G\right) \geq \cdots\geq\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\geq2$ and $n\geq15\left(s-1\right) ,$ then \[ \left\vert \mu_{s}\left(G\right) \right\vert +|\mu_{s}(\overline{G})|\,\leq n/\sqrt{2\left(s-1\right)}-1. \] Also if $s\geq1$ and $n\geq4^{s},$ then \[ \left\vert \mu_{n-s+1}\left(G\right) \right\vert +|\mu_{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.