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 and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.