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

Question

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,

• Weighted undirected graphs, complex Laplacian, complex eigenvalues & spectral clusering

• symmetric normalized Graph Laplacian and symmetric normalized Adjacency matrix eigenvalues

Answer 1

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.