A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the corresponding degree sequences $d_U$ and $d_V$, then it is easy to see that the largest eigenvalue $\lambda_{\max}$ satisfies $$ \sqrt{\|d_U\|_2\|d_V\|_2} \le \lambda_{\max} \le \sqrt{\|d_U\|_\infty\|d_V\|_\infty}; $$ in particular, if the graph is $(r_U,r_V)$-regular, then $\lambda_{\max}=\sqrt{r_Ur_V}$. (A reference, particularly for the double inequality above, will be appreciated.) In the general case, the largest eigenvalue also reflects in some way the "average degree" of a vertex - but is anything more specific known about it? To put it simply,

What properties of a (bipartite) graph can be read from its largest eigenvalue?

### A brief summary and common reply to all those who have answered so far.

Thanks for your interest and care!

To make it very clear: I am interested in the

*usual*, not*Laplacian*eigenvalues.Although the largest eigenvalue is related to the average degree, for non-regular graphs this does not tell much; hence, I believe, understanding the meaning of the largest eigenvalue in terms of the "standard" properties of the graph is of certain interest.

It is true that different bipartite graphs (as $K_{1,ab}$ and $K_{a,b}$) may have the same largest eigenvalue, but, I believe, this does not mean that the largest eigenvalue cannot be suitably interpreted.

I still could not find a reference to the displayed inequality above. (@kimball: Lovasz does not have it.)

Laplacian eigenvalues.) $\endgroup$ – Seva May 1 '11 at 16:06