# Strongly regular graphs with the same parameters as Paley graph

It is known that the Paley graph $P(q)$ for $q = 5, 9, 13$ or $17$ vertices are the only strongly regular graph with the parameters as $P(q)$.

If $q \geq 25$, is the following assertion true:

There are strongly regular graphs $G$ with the same parameters as $P(q)$ such that $G\not\cong P(q)$.

## 1 Answer

If $p$ is a prime congruent to 3 (mod 4) and $q$ is an even power of $q$, there are the Peisert graphs which are arc-transitive, self-complementary conference graphs, not isomorphic to Paley graphs.

More generally, start with the affine plane over $GF(q)$ where $q$ is odd, with point set $GF(q)\times GF(q)$. Choose a subset $P$ of $GF(q)\cup\infty$ and define $X(P)$ to be the graph with the points of the plane as vertices, with two points adjacent if they are distinct and the slope of the affine line joining them is in $P$. Then $X(P)$ is strongly regular, and if $|P|=(1+q)/2$, then $X(P)$ is a conference graph. When $q$ is large, we get many non-isomorphic graphs. (The Peisert graphs can be obtained in this way.)

For more on these topics, see Natalie Mullin's Ph.D. thesis (http://uwspace.uwaterloo.ca/bitstream/10012/4264/1/nm_thesis.pdf)

As you can see from Brouwer's tables (http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html), there are 41 conference graphs on 29 vertices. According to the same source, conference graphs on fewer than 25 vertices are Paley graphs and there are 15 conference graphs on 25 vertices.

I do not recall seeing any general procedure for constructing conference graphs on a prime number of vertices that are not isomorphic to Paley graphs.