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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ mathoverflow.net/questions/129397/… $\endgroup$
    – Brendan McKay
    Jul 16, 2015 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, 2015 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, 2015 at 16:45

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
0

Your Answer

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

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