Given the adjacency matrix $A_{ij}$ of a graph with $N$ vertices and $M$ links (or any binary symmetric matrix of size $N \times N$), is it possible to establish lower and upper boundaries of its eigenvalues? I mean, do $N$ and $M$ determine the lowest and the largest possible eigenvalues of the matrix?
In other words, let $L$ be the Lapacian of $A_{ij}$. We know that its eigenvalues obbey the following: $\lambda_1 = 0 \leq \lambda_2 \leq \lambda_3 \leq \ldots \leq \lambda_N$. The lowest eigenvalue is always $\lambda_1 = 0$ and hence, the eigenvalues of $L$ have a lower bound. Is there an upper bound for $\lambda_N$ that depends only on the size $N$ of the graph and/or on $M$?
Stated yet in another manner. Does anyone know a graph $G'$ whose $\lambda'_N$ is largest than the $\lambda_N$ of any other graph of the same size $N$ and/or number of links $M$?
Thank you!
Best Answer
There are several notions of Laplacian for graphs. For instance, there is the normalized Laplacian, the classical Laplacian and Laplacians with boundary conditions as the Dirichlet Laplacian and so on. Assuming that you are taking about the classical Laplacian then its eigenvalues are $$ 0=\lambda_1\leq \lambda_2\leq \ldots\leq\lambda_{n} $$ where $n$ is the number of nodes. Typically it is $\lambda_2$ the eigenvalue that gives the most information about the graph (like expanding properties, connectivity, isoperimetric properties, etc). For instance, $\lambda_2>0$ iff the graph is connected.
Here are a few known results:
[Fiedler] $\lambda_2\leq \frac{n}{n-1}\min\{d(v):v\in V\}$ where $d(v)$ is the degree of the node $v$.
[Anderson and Moreley] The maximum eigenvalue satisfies $$ \lambda_n\leq\max\{ d(u)+d(v):uv\in E\}. $$ If the graph $G$ is connected then the equality holds iff the graph is bipartite.
[Kelmans] If the graph is simple (no multiple edges or loops) then $\lambda_n\leq n$ with equality iff the complement of $G$ is not connected.
$\sum_{i}^{n}{\lambda_i}=2m=\sum_{v}{d(v)}$ where $m$ is the number of edges in $G$.
[Fiedler] $\lambda_{n}\geq \frac{n}{n-1}\max\{d(v):v\in V\}$.
The second and last bullet give you lower and upper bounds for the maximum eigenvalue in terms of the degree of the nodes. If the graph is regular of course much more can be said.
I hope it helps!