MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 6 down vote accepted

This page 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:

share|cite|improve this answer
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 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: – Emil Sep 19 '10 at 21:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.