Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

2012-07-04T17:35:21Z

This question is motivated by a talk I went to earlier today.

Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.

Let $$\lambda_1\geq \lambda_2 \geq\dots \geq \lambda_n$$ be the eigenvalues of $A$, so in particular $\lambda_1=d$. If the first two eigenvalues are the same, that is $\lambda_2=\lambda_1$, then it tells us a lot about the structure of the graph. In particular, the graph must be disconnected. (This is an if and only if condition)

What if the second and third eigenvalues are equal? That is, suppose that $\lambda_1>\lambda_2=\lambda_3$. What does that tell us (if anything) about the structure of the graph?

Additional questions: If $\lambda_1=\lambda_2=\cdots=\lambda_k<\lambda_{k+1}$, then the graph will have exactly $k$ connected components. What can we say about $G$ if $\lambda_1<\lambda_2=\cdots=\lambda_{k+1}<\lambda_{k+2}$? That is, the second eigenvalue has multiplicity $k$.

What if the $n^{th}$ eigenvalue has multiplicity $k$?

Answer by Chris Godsil for Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

2012-07-04T21:24:37Z

It you allow weighted adjacency matrices and if you insist (among there things) that the eigenspace associated to $\lambda_2$ satisfies the "strong Arnold condition", then you are dealing the Colin de Verdiere invariant. For this, the best I can do now is to refer you to the wikipedia article on this invariant.

But you question is what can be said about connected graphs where $\lambda_1$ has multiplicity greater than one. The short answer is: very little. One reason for this that if our graph was associated with some physical of chemical system, than having $\lambda_2$ very close to $\lambda_3$ will have much the same effect as having $\lambda_2=\lambda_3$. There are certainly no results on graph spectra that relate properties of a graph to whether or not $\lambda_2$ is simple.

It is true that the existence of non-trivial automorphisms can prevent all eigenvalues from being simple. The classic result of this type is that if the automorphism group of a graph is vertex transitive, then its eigenvalues can not all be simple. Stronger assumptions may give more, since each eigenspace provides a representation of the automorphism group, and if one of these representations is faithful, then the multiplicity is at least the minimum degree of an irreducible representation of the group.

On the other hand though, having eigenvalues of large multiplicity tells us nothing about the automorphism group. Strongly regular graphs have large multiplicities, but in general no non-trivial automorphisms.

Repeated Second Eigenvalue of the Adjacency Matrix of a Graph - MathOverflow

Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

Answer by Chris Godsil for Repeated Second Eigenvalue of the Adjacency Matrix of a Graph