eigenvalue estimate of the adjacency matrix The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$.  A very easy upper estimate for it can be obtained directly by Gershgorin's theorem:
$$
\lambda_{\max}\le \Delta\ ,
$$
where $\Delta$ is the maximal degree of the graph. Are any further estimates known?
And are there known lower estimates on the lowest eigenvalue $\lambda_\min$?
 A: A classic estimate is due to Constantine:
$$
\lambda_{\min} \geq -\sqrt{\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor}.
$$
If $m$ is the number of edges, then
$$
\lambda_{\min} \geq - \sqrt{m}.
$$
A common generalization is
$$
\lambda_{\min} \geq -\sqrt{MaxCut(G)},
$$
where $MaxCut(G)$ is the size of a maximal bipartite subgraph.
You can find these results, with references, in the 2008 paper by Bell et al.. There are more complicated results as well, in particular using the eigenvector.
If you would like to discuss such topics, I am always interested.
A: Not very different, but another possible estimate is the following: if you know that $Av\leq tv$ (elementwise) for some nonnegative (elementwise) vector $v$ and real $t$, then $\lambda_\max \leq t$ (proof: left-multiply by the left Perron vector. Irreducibility is needed, otherwise you need $v>0$). This is essentially a "weighted Gershgorin estimate", since Gershgorin's theorem corresponds to the version with $v$ the vector of all ones.
Note that both estimates can be tight, if $v$ is the Perron eigenvector.
You may get other estimates via matrix norms: $\lambda_\max \leq ||A||$. Computing the Euclidean norm is as difficult as computing the maximum eigenvalue, so it is probably unhelpful. This leaves as candidates the Frobenius norm (which is always larger than the Euclidean norm, but at least it is easily computable) and the $1$ norm (which is the Gershgorin bound on $A^T$ --- so yes, I am basically just stating Gershgorin variants and easy stuff in this answer, sorry).
