Hello!
There are two definitions of graph spectrum:
1) Eigenvalues of adjacency matrix $A$.
2) Eigenvalues of Laplacian of adjacency matrix ($L$).
Different sources offer different properties based on this two definitions.
Of course it's painful to compute two different spectrums if adjacency matrix is big.
So, the question is:
Is there a method to connect one vector of eigenvalues ($\Lambda(A)$) with another ($\Lambda(L)$)?
It is obvious that
$L = T^{-1/2}(T-A)T^{-1/2} = E – T^{-1/2}AT^{-1}T^{+1/2}$, where
$T$ is the diagonal matrix with $t_{v,v}=d_v$, and $t_{u,v}=0$, if $u\ne v$,
and $t^{-1}_{v,v}=0$, if $d_v=0$,
$d_v$ – degree of $v$.
Also, when $G$ is $k$-regular, $L=I-\frac{1}{k}A$, so $\Lambda(L)=1-\frac{1}{k}\Lambda(A)$.
But in general case it's like I need to compute eigenvalues of $AT$, if I know eigenvalues of $A$. ($T$ is diagonal).
Thanks for any help.
Best Answer
Essentially your question is equivalent to asking for the relation between the spectrum of $A+D$ and $A$, where are $A$ is symmetric, $D$ is diagonal and both matrices are real. And, by change of basis, this is equivalent to asking for the relation between the spectrum of $A+B$ and $A$ when $A$ and $B$ are real symmetric. A lot of thought has been given to this question. The short summary is that eigenvalues of $A$ provide no information useful towards computing the eigenvalues of $A+D$.
It might also be worth pointing out that there are many more than two definitions of graph spectrum (normalized and unsigned Laplacian, Seidel, spectrum of complement, to mention four more that come quickly to mind). All of these provide the same information for regular graphs, but in no case does computing one provide much help in computing another.