# Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

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$?

-
The $d$-eigenspace is rather special. It corresponds to the kernel of the Laplacian which can be naturally identified with the space of locally constant functions on $g$ ("harmonic functions"). A similar interpretation doesn't exist for smaller eigenvalues so I don't expect their multiplicities to have a similar direct meaning. However, large multiplicities of eigenvalues in general suggest (but don't imply) that $G$ has nontrivial symmetries. –  Qiaochu Yuan Jul 4 '12 at 19:52
@Qiaochu: Here is one example which may count. If $\lambda_2$ has multiplicity $n-1$, that is all other eigenvalues are the same, then I believe that $G$ must be the complete graph. –  Eric Naslund Jul 4 '12 at 20:55
It would imply that the graph can be "partitioned" into two weakly connected components, in two different ways. –  Piyush Grover May 31 '13 at 20:21
Such results are studied in machine learning and dynamical systems communities, under various terms such as "spectral clustering", "Almost-invariant sets", "metastable sets" etc. They look at the eigenspectrum of graph Laplacian, rather than the Adjacency matrix itself, though. –  Piyush Grover May 31 '13 at 20:24

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.