show/hide this revision's text 4 added 627 characters in body; added 33 characters in body

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?

NB:

thanks for

A brief summary and common reply to all those who replied have answered so far, but - to .

  1. Thanks for your interest and care!

  2. To make it very clear: I am interested in the "usual", usual, not Laplacian eigenvalues!.

  3. 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.

  4. 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.

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

show/hide this revision's text 3 deleted 3 characters in body

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?

NB:###

NB:

thanks for all those who replied so far, but - to make it very clear: I am interested in the "usual", not Laplacian eigenvalues!
show/hide this revision's text 2 added 249 characters in body; added 4 characters in body; added 5 characters in body

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_1,r_2)$(r_U,r_V)$-regular, then $\lambda_{\max}=\sqrt{r_1r_2}$\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?

NB:###

thanks for all those who replied so far, but - to make it very clear: I am interested in the "usual", not Laplacian eigenvalues!
show/hide this revision's text 1