12
$\begingroup$

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive.

This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is there an example on less vertices?

Thanks for all replies.

$\endgroup$
  • 1
    $\begingroup$ mathoverflow.net/questions/129397/… $\endgroup$ – Brendan McKay Jul 16 '15 at 4:26
  • $\begingroup$ @BrendanMcKay Thanks a lot for the link. So this gets me an example of 25 vertices, and no nontrivial automorphisms. Still wondering if non-vertex transitive can be even smaller... $\endgroup$ – Josh Jul 16 '15 at 4:45
  • 1
    $\begingroup$ A minor comment: Problem 20c in Biggs "Algebraic Graph Theory" 2nd Ed. shows a simple construction of a strongly regular graph on 26 vertices that is not vertex-transitive. $\endgroup$ – Sebi Cioaba Aug 7 '15 at 16:45
13
$\begingroup$

There is no smaller example.

Various places, including Andries Brouwer's list of parameters and existence for small SRGS (http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html) show that there are only a handful of parameter sets to check.

Those with fewer than 25 vertices can almost be checked by hand as they fall into a few families (Paley graphs) or are well-known individual graphs (e.g Clebsch graph).

For the parameter set $(25, 12, 5, 6)$ there are exactly $15$ graphs and they have automorphism groups of orders $1$ (twice), $2$ (four times), $3$ (twice), $6$ (four times), $72$ (twice) and $600$.

$\endgroup$

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.