Spectra of Graphs

Question

Suppose $G$ is simple (no loops or multiple edges) graph of order $n$. Its adjacency eigenvalues $\lambda_1\geq \lambda_2\geq \cdots\geq \lambda_n$ satisfy $\lambda_1+\lambda_n+\cdots+\lambda_n=0.$ I'm wondering if there is anything to be said about the spectra of all such graphs $G$, viewed a subset of $\mathbb{R}^n$. That is define the set $$\Omega=\{(x_1, \ldots ,x_n)\,:\, x_1\geq x_2\geq \cdots \geq x_n \mbox{ are the eigenvalues of some simple graph }G\}. $$ Can anything interesting be said of the set $\Omega$ ?

Answer 1

There are bounds for the largest and the smallest eigenvalue of the adjacency matrix $A$ associated with the graph $G$. For instance, if $|G|=n$, one can prove that $$\lambda_n\geq-\sqrt{(n/2)[(n+1)/2]},$$ where $[x]$ denotes the largest integer not greater than $x$. Thus the set $\Omega$ must satisfy $$x_n\geq-\sqrt{(n/2)[(n+1)/2]}.$$ These bounds are obtained using that there exits orthonormal vectors $u_n$ such that $u_n^*\cdot A\cdot u_n=\lambda_n$.