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?
3
-
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 ♦Commented Apr 12, 2014 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$– user49525Commented Apr 14, 2014 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 ChoiCommented May 12, 2014 at 23:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered Apr 12, 2014 at 13:59
-
$\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$ Commented Apr 12, 2014 at 15:28
-
$\begingroup$ Your comment is correct for the matrices, but you asked about the spectrum. $\endgroup$ Commented Apr 12, 2014 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$ Commented Apr 12, 2014 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$ Commented Apr 12, 2014 at 17:50
-
$\begingroup$ So there is no proper relation between these two spectra? @ChrisGodsil $\endgroup$ Commented Apr 14, 2014 at 4:33