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](https://arxiv.org/pdf/0801.2322.pdf)). 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.



Smallest pair of non-isomorphic graphs equivalent under the Weisfeiler-Leman algorithm
The 15-vertex "strongly regular" tournament is the smallest non-Schurian
example of an association scheme; it is [unique](http://math.shinshu-u.ac.jp/~hanaki/as/) as an assoc. scheme (there is no Schurian scheme with these parameters - but see PS below!). The smallest case of two non-isomorphic association schemes with the same parameters needs 16 vertices. These were results of calculations I did over 30 years ago using a Fortran IV program written to enumerate association schemes---which is unfortunately lost. It was roughly following the "Russian school" methodology of enumeration of strongly regular graphs (and was a 2-year course work done under supervision of Igor Faradjev, one of pioneers of constructive enumeration). 


These results were confirmed years later by a group in Japan---they wrote their own code to do this [enumeration](https://web.archive.org/web/20010714072524/http://goldenfish.math.kyushu-u.ac.jp/Suga/ass/class.htm). Up-to-date tables
are [here](http://math.shinshu-u.ac.jp/~hanaki/as/). 




---


PS. The smallest pair of non-isomorphic "strongly regular" tournaments indeed needs 15 vertices: in the corresponding (unique) association scheme there are two digraphs, obtained one from the other by reversing the orientation - but this operation is obviously not an isomorphism, and in fact there is no isomorphism (according to computer calculations using Sagemath).


