What graph Laplacians commute

Question

I know that the graph Laplacian of a fully connected graph commutes with the Laplacian of any other graph.

Is there any theorem stating something similar about some more general family of graphs? I'm specially interested to know if there's any result about sparse random graphs.

Thanks.

--EDIT (Re-statement): What Laplacians commute with a -given- Laplacian? One answer is all of its powers and their linear combination (see:Given a matrix, is there always another matrix which commutes with it?) Are there other graphs (a more general family) with this property?

Answer 1

Let $X_{ij}$ be the graph on $n$ vertices with exactly one edge, joining $i$ to $j$. The Laplacian of $X_{ij}$ is $(e_i-e_j)(e_i-e_j)^T$. It's not difficult to check that if this commutes with the Laplacian $L$ of a graph $G$ and $v$ is a vertex of $G$ not $i$ or $j$, then $v$ is adjacent to $i$ if and only if it is adjacent to $j$.

It follows that if $L$ commutes with the Laplacian of $X_{ij}$ for all $i$ and $j$, then $G$ is a either a complete graph, or the graph with no edges.