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.)
Best Answer
(This is just an overlong comment.)
A basic problem is that the complete bipartite graphs $K_{1,ab}$ and $K_{a,b}$ have the same spectral radius, and these graphs would not usually be viewed as similar. And, of course, all $k$-regular bipartite graphs have the same spectral radius.
Also if $A$ is the adjacency matrix of some graph, then the spectral radius of the bipartite graph with adjacency matrix $$\left( \begin{array}{cc} 0 & A \\\ A & 0 \end{array} \right)$$ is the square of the spectral radius of $A$. So the question as to what properties of a graph are determined by its spectral radius is a subcase of your question. (I am not arguing that the two problems are equivalent.)