3
$\begingroup$

So the Laplacian matrix of an undirected graph $G$ is $L(G)=D(G)-A(G)$, where $D(G)$ is the diagonal degree matrix and $A(G)$ is the adjacency matrix, as usual.

I can easily prove the case when the other graph $H$ is regular but with a different order, using the trace. But I'm struggling with the non-regular case.

$\endgroup$
3
$\begingroup$

Let the degrees of the graph $G$ be $d_1, d_2, \dots, d_n$.

Then the trace of $L(G)$ gives us the sum $\sum_{i=1}^n d_i$. On the other hand, the trace of $L(G)$ is the sum of the eigenvalues; therefore $\sum_{i=1}^n d_i$ is determined by the Laplacian spectrum.

In $L(G)^2$, the diagonal entries are $d_1^2 - d_i, \dots, d_n^2 - d_n$, so the trace of $L(G)^2 + L(G)$ gives us the sum $\sum_{i=1}^n d_i^2$. On the other hand, this trace can also be computed from the eigenvalues: it is $\sum_{i=1}^n (\lambda_i^2 + \lambda_i)$. Therefore $\sum_{i=1}^n d_i^2$ is also determined by the Laplacian spectrum.

Therefore the spectrum of $G$ lets us compute $$ n \sum_{i=1}^n d_i^2 - \left(\sum_{i=1}^n d_i\right)^2 = \sum_{i \ne j} (d_i - d_j)^2 $$ which is $0$ if and only if the graph is regular. (This is essentially the equality case of the Cauchy-Schwarz inequality.) As a result, it's also determined by the Laplacian spectrum of $G$ whether or not $G$ is a regular graph; a regular graph cannot be cospectral with a non-regular one.

(Source: Which graphs are determined by their spectrum? by van Dam and Haemers.)

$\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.