# What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency matrix) eigenvalue?

There are two other related unanswered questions that I found,

• in the regular case (in which every node has the same degree) the multiplicity of the largest adjacent eigenvalue is the dimension of the kernel of the laplacian, that is the number of connected component of a graph Nov 24 '14 at 10:35
• @Exodd But that is the smallest eigenvalue of the Laplacian of the regular graph - right? You know anything about the largest Laplacian eigenvalue in general? Nov 24 '14 at 15:07

## 1 Answer

There are graphs on $n^2$ vertices with largest Laplacian eigenvalue of multiplicity $n^2-3n+2$.

These graphs are the so-called Latin square graphs. For details of their construction see, e.g., http://www.cs.yale.edu/homes/spielman/561/2009/lect23-09.pdf. The summary is that from an $n\times n$ Latin square we get a graph on $n^2$ vertices, regular of degree $3n-3$. The least eigenvalue of its adjacency matrix is $-3$ with multiplicity $n^2-3n+2$; it becomes an eigenvalue $3n$ of the Laplacian, and this is the largest.