Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph

Abstract

Terpai [22] proved the Nordhaus-Gaddum bound that $\mu (G)+\mu (\overline{G})\le 4n/3-1$, where $\mu (G)$ is the spectral radius of a graph $G$ with $n$ vertices. Let $s^{+}$ denote the sum of the squares of the positive eigenvalues of $G$. We prove that $\sqrt{s^{+}(G)}+\sqrt{s^{+}(\overline{G})}<\sqrt{2}n$ and conjecture that $\sqrt{s^{+}(G)}+\sqrt{s^{+}(\overline{G})}\le 4n/3-1.$ We have used AutoGraphiX and Wolfram Mathematica to search for a counter-example. We also consider Nordhaus-Gaddum bounds for $s^{+}$ and bounds for the Randić index.

9 pages