3
$\begingroup$

As the title says, let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?

I suspect the most likely counterexample would be $|S|=1$.

$\endgroup$
4
  • $\begingroup$ 1) Is your question about finite graphs? 2) Does "given parameters" means that, in the language of en.wikipedia.org/wiki/Strongly_regular_graph, the integers $k$ (degree), $\lambda$ and $\mu$ (number of common vertices between any two adjacent, resp. non-adjacent vertices), are fixed? Or do you also fix the number $v$ of vertices [this is not a local assumption, so it sounds less natural]? $\endgroup$
    – YCor
    Mar 24, 2016 at 10:30
  • $\begingroup$ @YCor 1) Finite graphs. 2) All parameters, including the number of vertices: $(v,k,\lambda,\mu)$. $\endgroup$
    – joro
    Mar 24, 2016 at 10:34
  • $\begingroup$ For many primes (e.g., $p=19$ by Jordan, see www-groups.mcs.st-and.ac.uk/~colva/dartmouth.pdf p.9), the only transitive groups on $p$ elements are symmetric, alternating or of affine type. So picking $v$ to be such a number, if you have a strongly regular connected graph on $v$ vertices that is not a complete graph, and whose automorphism group does not have a normal subgroup of order $p$, then you're done. $\endgroup$
    – YCor
    Mar 24, 2016 at 10:58
  • $\begingroup$ A strongly regular graph on $p$ vertices ($p$ prime) is necessarily a conference graph, consequently $p\equiv1$ mod 4 and therefore there is a Paley graph on $p$ vertices. $\endgroup$ Mar 24, 2016 at 12:05

1 Answer 1

9
$\begingroup$

There are exactly 10 strongly regular graphs with parameters (26,10,3,4), none of which are vertex-transitive. The graphs can be found on Ted Spence's webpage.

$\endgroup$
4
  • $\begingroup$ One can also mention that these graphs, with orbits, are given on pages 175-179 of Lect. Notes Math. vol 558, Springer 1976. $\endgroup$ Mar 24, 2016 at 19:13
  • $\begingroup$ Krystal, thank you for the answer and the links. $\endgroup$
    – joro
    Mar 25, 2016 at 7:24
  • $\begingroup$ @DimaPasechnik Did you verify the result? The graphs are in weird format. $\endgroup$
    – joro
    Mar 25, 2016 at 7:25
  • $\begingroup$ @joro No doubts about the LMN result. I happen to know authors, I worked at the same lab some 10-15 years later... Also independently obtained by Paulus $\endgroup$ Mar 25, 2016 at 7:42

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.