4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 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 Sep 19 '10 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 Sep 19 '10 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 Sep 19 '10 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 Sep 19 '10 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 Sep 19 '10 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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