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.