Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
1  
@Chris: Many Thanks –  Alireza Abdollahi Jan 22 '13 at 19:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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