The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few lower bounds on the smallest eigenvalue are known in the literature, but I could not find any upper bound. Hence my question: What is known about this? Do there exist graphs whose adjacency matrix is positive semi-definite?
Best Answer
Since the eigenvalues are real, and since their sum is the trace of $A$, which is zero, we see that either all eigenvalues are zero, or there are both positive and negative eigenvalues. So no non-empty graph has a positive semidefinite adjacency matrix.
I do not think there is much in the way of upper bounds on the least eigenvalue. For more regular graphs there are bounds on the size of cliques and cocliques that involve the least eigenvalues, and these can be rearranged to get upper bounds on the least eigenvalue. So if $X$ is $k$-regular on $v$ vertices and the max size of a coclique is $a$, then we have an upper bound
$$-\frac{k}{\frac{v}a -1}$$
Here I am just using the Hoffman bound on the size of a coclique.