Let G be an undirected graph, then Laplacian Matrix(L(G)) = Degree Matrix (D(G)) - Adjacency Matrix (A(G)). What is the relationship between laplacian and adjacency spectrum of undirected graphs?


closed as too broad by Matthew Kahle, Stefan Kohl, Misha, Yemon Choi, Chris Godsil May 13 '14 at 0:54

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What do you already know about this? From what background are you coming at the problem? This will help potential answerers. $\endgroup$ – David Roberts Apr 12 '14 at 11:39
  • $\begingroup$ We already have an adjacency spectrum then what is the advantage of laplacian spectrum over adjacency spectrum and as these two matrices are related, there must exist some relationship between their spectra right? $\endgroup$ – user49525 Apr 14 '14 at 4:36
  • $\begingroup$ "there must exist some relationship between their spectra right?" Well, why do you think there is a relation between the spectra of the sum of two matrices and the spectra of the individual matrices? (Some things can be said for Hermitian matrices, but they are probably harder and deeper and less precise than what you seem to be hoping for.) $\endgroup$ – Yemon Choi May 12 '14 at 23:56

The short answer is that, if your graph is not regular, there is no relation. The effect on the eigenvalues of adding a diagonal matrix is the same as adding an arbitary symmetric matrix.

  • $\begingroup$ I think this answer is not quite correct: there obviously is a relation, as the two matrices determine each other, just no one knows how to describe it :) $\endgroup$ – Alex Degtyarev Apr 12 '14 at 15:28
  • $\begingroup$ Your comment is correct for the matrices, but you asked about the spectrum. $\endgroup$ – Chris Godsil Apr 12 '14 at 16:28
  • $\begingroup$ Hmm... I didn't ask. So, can you prove that there's no relation whatsoever? Meaning, that every pair of spectra can be realized by the two matrices of the same graph? $\endgroup$ – Alex Degtyarev Apr 12 '14 at 16:48
  • 1
    $\begingroup$ I offered only the "the short answer". For example, if the graph has one vertex of degree $k$ and the rest have degree $\ell$, you can derive an interlacing result. But I have never seen anyone find a useful connection between the two spectra. $\endgroup$ – Chris Godsil Apr 12 '14 at 17:50
  • $\begingroup$ So there is no proper relation between these two spectra? @ChrisGodsil $\endgroup$ – user49525 Apr 14 '14 at 4:33

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