Can a regular graph have the same Laplacian spectrum with a non-regular one? 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.
 A: 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.)
