Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
1  
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
1  
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
3  
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
1  
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

Your Answer

 
discard

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.