Let $G$ be a connected, undirected graph. Define graph Laplacian as
$$L_{G} = D^{-1}(D – A) = I – D^{-1}A,$$
where $D$ is a diagonal matrix of degrees and $A$ is an adjacency matrix.
Question: Let $G, H$ be two connected non-isomorphic graphs such that $L_{G}$ and $L_{H}$ have simple spectrum (all eigenvalues have multiplicity $1$). Is it true that Weisfeiler-Lehman test (1-WL test) will distinguish $G$ and $H$? I.e.
$$WL(G) \neq WL(H) ?$$
I found that there exist non-isomorphic cospectral graphs with simple spectrum (e.g. this post), but it seems that WL test distinguishes them easily.
Note that my $L_{G}$ and symmetrically normalized Laplacian $L_{sym} = I – D^{-1/2}A D^{-1/2}$ have the same spectrum, if it helps in any way.
Best Answer
The two graphs below appear to be a counterexample. (Their Graph6 codes are
M{O_o_H@?G?R?S?I_andM{O_o_G@OG?T?Q?K_.)For both graphs, the eigenvalues of $I - D^{-1}A$ are approximately $$ \{0.,0.258501,0.357451,0.513408,0.609971,0.793989,0.941916,1.14507,1.22963,1.27731,1.53934,1.68564,1.82071,1.82706\} $$ which are all distinct. We can't distinguish them by eigenvalues, and (as far as I can tell) the Weisfeiler-Lehman just looks at them, shrugs, and gives up, since they are both regular: at each stage of the test, all vertices with have identical labels.