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$

1 Answer 1

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$
6
  • 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$ 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$ 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$ 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$ 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
    Sep 19, 2010 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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