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,

  • $\begingroup$ 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 $\endgroup$
    – Exodd
    Nov 24, 2014 at 10:35
  • $\begingroup$ @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? $\endgroup$
    – user6818
    Nov 24, 2014 at 15:07

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .