The first eigenvalue of a graph - what does it reflect?

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.

1. Thanks for your interest and care!

2. To make it very clear: I am interested in the 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.)

-
The largest eigenvalue of which matrix? – thei May 1 2011 at 8:43
@thei: the eigenvalues of a graph are the eigenvalues of its adjacency matrix. – Seva May 1 2011 at 8:58
They can also be the eigenvalues of the Laplacian of the graph. – thei May 1 2011 at 9:40
@thei: I see. No, I mean "usual" eigenvalues. (Otherwise, I would write Laplacian eigenvalues.) – Seva May 1 2011 at 16:06

Assume the graph is connected.

Let $\left| 1 \right>$ be the vector of all 1's (in Dirac notation), and let $A$ be the adjacency matrix. Then $\left<1|A|1\right>$ is the number of edges of the graph (well, actually twice the number of edges). Similarly, $\left<1|A^n|1\right>$ is the number of paths of length $n$, where a path is a sequence of vertices with consecutive vertices connected, repetitions allowed in the case of loops. Call this $P_n$.

Since the graph is connected, its adjacency matrix is irreducible and by the Perron-Frobenius theorem the first eigenvalue is simple and the eigenvector $\left| v \right>$ has positive components. Therefore, $\left< v | 1 \right> > 0$, allowing use of the power iteration method. As $n \to \infty$, $A^n\left|1\right>$ approaches the first eigenvector of $A$ (aside from normalization). So, $$\lim_{n \to \infty} \frac{P_{n+1}}{P_n} = \lim_{n \to \infty} \frac{P_{2n+1}}{P_{2n}} = \lim_{n \to \infty} \frac{\left<1|A^n A A^n|1\right>}{\left<1|A^n A^n|1\right>} = \lambda_{\textrm{max}}.$$ The largest eigenvalue then tells how the number of paths of length $n$ grows, as $n$ grows (keeping in mind that I used a nonstandard definition for "path"). Furthermore, the limit written above approaches $\lambda_\textrm{max}$ from below.

Theorem 4 of Yu, Lu, Tian (2004) is equivalent to $\lambda_\textrm{max} \ge \sqrt{P_4 / P_2}$, but is expressed in terms of the degrees and 2-degrees of the vertices.

-
 To be clear, by a path of length $n$ I mean a sequence of vertices $(a_0, a_1, \dots, a_n)$, with repetitions allowed, with the property that consecutive vertices in the sequence are connected by an edge. By "counted twice" I mean that if $(a_0, \dots, a_n)$ is a path then so is $(a_n, \dots, a_0)$. In particular, when $n=1$, this is twice then number of edges since both $(a_0,a_1)$ and $(a_1,a_0)$ get counted. – Dan Stahlke Aug 19 at 13:46

The largest eigenvalue $\Lambda (A)$ of the adjacency matrix $A$ of a general graph satisfies the following inequality:

$\max \ ( d_{av},\sqrt{d_{max}} ) \le \Lambda (A) \le d_{max}$ ,

where $d_{av}$ is the average degree of nodes in the graph and $d_{max}$ is the largest degree.

The proof of this inequality is found in the small survey I wrote about the most important spectral properties of a graph here. You can also check the references in the report for more detailed properties.

-

The few times I have ever worked with eigenvalues of graphs, it has been in relation to the path algebra of the graph; each path in the graph is an element of this algebra. At any rate, the characteristic polynomial of the graph gives exact recurrences for calculating the number of paths of a given length and in particular the largest eigenvalue will give the asymptotic growth rate of the number of paths of different lengths. This asymptotic growth is true if the largest eigenvalue has modulus larger than all other eigenvalues of the graph. If there are multiple eigenvalues of maximum modulus then the asymptotics of the path-growth function will change although offhand I don't know if having multiple eigenvalues of the same maximal modulus is actually possible (perhaps someone who does more graph theory than I would care to comment on this).

-
Regarding multiple eigenvalues of the same maximum modulus, it is certainly possible if the graph is directed or has multiple components; if the graph is connected and undirected, then this is ruled out by Perron-Frobenius. – Qiaochu Yuan May 2 2011 at 15:48
Perron-Frobenius doesn't quite rule out the possibility and it is realized for bipartite graphs. – Douglas Zare May 2 2011 at 20:43
@Douglas: I believe it does. Could you give an example of a (simple, undirected) connected graph with the maximum eigenvalue of multiplicity larger than $1$? – Seva May 3 2011 at 5:40
@Seva I meant that if $\lambda$ is an eigenvalue of a bipartite graph, then so is $-\lambda$ which has the same modulus. This is the only way another eigenvalue can have the same modulus as the principal eigenvalue for an undirected graph. Connected undirected graphs so that no power of the adjacency matrix has all positive entries are bipartite. – Douglas Zare May 15 2011 at 15:32

I am not at all an expert on this, but I believe that the largest eigenvalue plays a role in several graph processes that people working in "network science" are interested in. A google search for "largest eigenvalue network" brought up this paper whose abstract begins "The largest eigenvalue of the adjacency matrix of a network plays an important role in several network processes (e.g., synchronization of oscillators, percolation on directed networks, linear stability of equilibria of network coupled systems, etc.)"; see references in the first paragraph of the paper to substantiate this claim.

-

Lovasz seems to think the largest eigenvalue is not so interesting (if the graph is connected), but the first gap tells you more.

www.cs.elte.hu/~lovasz/eigenvals-x.pdf

I believe this contains the double inequality you mentioned also. I also found some slides that give some motivation for looking at the largest eigenvalues:

math.uprm.edu/~xryong/SelectedTalks/Summer08-1.pdf

-

(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.)

-
 A comment on your first point ($K_{1,ab}$ vs $K_{a,b}$): this shows that, as expected, the largest eigenvalue reflects some kind of average of the degree sequence of a graph, rather than its structure. – Seva May 6 2011 at 6:35 I agree. But it seems to be hard to make the connection more precise without introducing some complicated average, and then you might just as well use the spectral radius itself. – Chris Godsil May 6 2011 at 12:26

Please find here some relations between the eigenvalues of the Laplacian and properties of the graph. You can also take a look at Fan Chung's book "Spectral Graph Theory" where many properties are discussed and the first four chapters are available online here.

-
It's Fan, not Fang. – Kimball May 1 2011 at 18:05
It's she, not it! – Seva May 1 2011 at 18:34

I fear my answer may not directly address the question, but I like the question!

Suppose we wish to numerically approximate solutions of the Poisson problem on a given domain. One strategy is to 'mesh' the region by simplices, and seek information on the nodes. One can approximate the Laplacian either strongly (finite differences) or weakly (finite elements) on the resultant graphs. The resultant matrices are symmetric and positive definite. Their largest eigenvalue reflect their condition number, which usually scales as $1/h^2$ as the length of edges $h \rightarrow 0.$ This condition number $\kappa:=|\lambda_{max}|/|\lambda_{min}|$ tells us how sensitive the computed solution will be to small errors in data, eg. due to rounding. Were I to change the data locally on one of the simplices, for example by marginally changing the location of one node, $\kappa$ predicts the worst amount by which computed solutions may change.

I conjecture there is a similar result in graph theory: given a graph, its largest eigenvalue provides a measure of how small changes to the graph structure influence flows on the graph. But I don't know enough about graph theory to even frame the conjecture precisely.

-