# Smallest non-isomorphic strongly regular graphs

Motivation: I want to see how the 3-dimensional Weisfeiler-Lehman algorithm (see Logical complexity of graphs, p. 14) distinguishes between two non-isomorphic strongly regular graphs srg(v,k,λ,μ) in a specific example.

Question: What are the smallest non-isomorphic strongly regular graphs with the same v,k,λ,μ?

## 1 Answer

This page http://www.maths.gla.ac.uk/~es/srgraphs.html lists some strongly regular graphs on few vertices, and gives two (16,6,2,2) graphs (which I didn't check but I presume they're non-isomorphic). I imagine they're the smallest possible but I haven't checked: http://www.maths.gla.ac.uk/~es/16.vertices

• The two (16,6,2,2) graphs are the Shrikhande graph and the line graph of $K_{4,4}$. The Shrikhande graph may be obtained by forming a 5x5 grid of squares, adding a diagonal in the same direction to each square, and gluing opposite edges of the square grid to form a torus. – David Eppstein Sep 19 '10 at 19:10
• I forgot to add: they are obviously nonisomorphic because the neighborhood of a vertex in the Shrikhande graph is a 6-cycle, whereas the neighborhood in the line graph of $K_{4,4}$ is a pair of 3-cycles. – David Eppstein Sep 19 '10 at 19:13
• Thanks for the clarification, David. Do you know if they are indeed the smallest, as they seem to be? – Andrew D. King Sep 19 '10 at 19:40
• Yes, e.g. in oai.cwi.nl/oai/asset/1817/1817A.pdf Brouwer and van Lint write that this is the only nonisomorphic pair with fewer than 25 vertices. – David Eppstein Sep 19 '10 at 20:04
• Peter Cameron discussed these graphs in a blog post recently: cameroncounts.wordpress.com/2010/08/26/the-shrikhande-graph – Emil Sep 19 '10 at 21:33