2
$\begingroup$

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,

$\endgroup$
  • $\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 '14 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 '14 at 15:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.