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
    Commented 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
    Commented 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
    Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .