Smallest non-isomorphic strongly regular graphs

Question

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,λ,μ?

Andrew D. King · Accepted Answer · 2010-09-19 18:23:51Z

6

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

answered Sep 19, 2010 at 18:23

Andrew D. King

1,8342 gold badges17 silver badges18 bronze badges

1

$\begingroup$ 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. $\endgroup$
– David Eppstein
Commented Sep 19, 2010 at 19:10
1

$\begingroup$ 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. $\endgroup$
– David Eppstein
Commented Sep 19, 2010 at 19:13
$\begingroup$ Thanks for the clarification, David. Do you know if they are indeed the smallest, as they seem to be? $\endgroup$
– Andrew D. King
Commented Sep 19, 2010 at 19:40
3

$\begingroup$ 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. $\endgroup$
– David Eppstein
Commented Sep 19, 2010 at 20:04
1

$\begingroup$ Peter Cameron discussed these graphs in a blog post recently: cameroncounts.wordpress.com/2010/08/26/the-shrikhande-graph $\endgroup$
– Emil
Commented Sep 19, 2010 at 21:33

| Show 1 more comment

1 Answer 1