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$.
$\begingroup$
$\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$– YCorCommented Mar 24, 2016 at 10:30
-
$\begingroup$ @YCor 1) Finite graphs. 2) All parameters, including the number of vertices: $(v,k,\lambda,\mu)$. $\endgroup$– joroCommented 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$– YCorCommented 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$– Chris GodsilCommented Mar 24, 2016 at 12:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\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$ Commented Mar 24, 2016 at 19:13
-
$\begingroup$ Krystal, thank you for the answer and the links. $\endgroup$– joroCommented Mar 25, 2016 at 7:24
-
$\begingroup$ @DimaPasechnik Did you verify the result? The graphs are in weird format. $\endgroup$– joroCommented 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$ Commented Mar 25, 2016 at 7:42