## Smallest non-isomorphic strongly regular graphs

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 1 Answer

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

-

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 2010 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 2010 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 2010 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 2010 at 20:04

1
Peter Cameron discussed these graphs in a blog post recently: cameroncounts.wordpress.com/2010/08/26/… – Emil Sep 19 2010 at 21:33
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8961517214775085, "perplexity_flag": "middle"}