There are pairs of non-isomorphic graphs that are indistinguishable by the k-WL (but distinguishable by (k+1)-WL) [1]. For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the 3-WL test cannot distinguish them [2].

I'm specifically looking for two non-isomorphic graphs that are indistinguishable by the 4-WL test. Are there two graphs with adjacency matrices in the literature, or existing implementations of [1] to generate such graphs?

[1] Cai, J. Y., Fürer, M., & Immerman, N. (1992). An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4), 389-410.

[2] Arvind, V., Fuhlbrück, F., Köbler, J., & Verbitsky, O. (2020). On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113, 42-59.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.