# Smallest pair of non-isomorphic graphs equivalent under the Weisfeiler-Leman algorithm

The (2-dimensional) Weisfeiler-Leman algorithm is a method for partitioning the ordered pairs of vertices of a graph in a canonical way which gives rise to a powerful graph invariant (see for instance Section 4 of this paper). If the partitions arising from two graphs are NOT "equivalent" in a certain sense, then the graphs cannot be isomorphic. However, there do exist graphs whose partitions resulting from the Weisfeiler-Leman algorithm are equivalent but are still non-isomorphic. The smallest such pair that I am aware of is the $4 \times 4$ rook graph (the Cartesian product of the complete graph $K_4$ with itself) and the Shrikhande graph. These are both strongly regular graphs with the same parameters, and any such pair of graphs are equivalent under the Weisfeiler-Leman algorithm. My question is, is this the smallest (in number of vertices) pair of non-isomorphic graphs that are equivalent under the Weisfeiler-Leman algorithm?

If we allow for directed graphs, then there are some strongly regular tournaments on 15 vertices that are equivalent under the Weisfeiler-Leman algorithm. Is there a smaller pair of non-isomorphic directed graphs that are equivalent under the Weisfeiler-Leman algorithm?

For what it's worth, this is the same as asking for the smallest pair of non-isomorphic graphs that admit an (weak) isomorphism between their coherent algebras that maps the adjacency matrix of the first graph to that of the second.

• Okay, I thought I could put two bounties on the same question because of what I read here: meta.stackexchange.com/questions/2786/… but apparently that is not possible. – David Roberson Feb 2 '18 at 11:01
• You probably might like to be more explicit about what exactly you mean by the invariant here. Note that you might start WL-algorithm with a regular graph and end up with "complete" coherent configuration, i.e. each edge and non-edge in an equivalence class of its own. I presume such examples are available for n<15 vertices. – Dima Pasechnik Feb 7 '18 at 0:31
• One needs to look at loop/(directed)-edge class sizes at each iteration, not only at the final stage. – Dima Pasechnik Feb 7 '18 at 9:38
• There are just two strongly regular tournaments on 15 vertices, one obtained from the other by reversing the orientation, and they are not isomorphic according to computer calculations. – Dima Pasechnik Feb 7 '18 at 11:10