MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the number of strongly regular graphs on $n$ vertices? or at least how many non-isomorphic strongly regular graphs can exist?

share|cite|improve this question
Thank you for every one who answer to the question. – Mojtaba Jazaeri Feb 5 '13 at 13:54
Thank you very much Professor Chris Godsil and professor Aaron Meyerowitz. – Mojtaba Jazaeri Feb 5 '13 at 17:54

No formula is known. Since Latin squares and Steiner triple systems give strongly regular graphs, lower bounds on the numbers of these structure give lower bounds if $n$ is square or if $n=v(v-1)/6$ and $v\equiv1,3$ mod 6. (Presumably these lower bounds are very weak.) According to Brouwer's tables we have exact enumeration up to 36; the numbers on 37 and 41 are not known. (I expect that the number of srgs on $p$ vertices, $p$ prime increases with $p$, but this has not been proved.)

Of course we do not know the number of isomorphism classes of graphs on $n$ vertices. We have a procedure that allows us to compute the number for moderate values of $n$, and we know that asymptotically the number is $2^{n(n-1)/2}/n!$. Given this, our knowledge for strongly regular graphs does not seem quite so bad.

share|cite|improve this answer
It is worth mentioning that the lower bounds in some case, while perhaps weak, are still enormous. The number of $m \times m$ latin squares is known to be greater than $\frac{m!^{2m}}{m^{m^2}}$ so I suppose this would be for $n=m^2$ and there is the mater of dividing out $m!^3$ to account for isomorphism/isotopys. But that is still a big number and accounts for both $n$ and the degree. Pairs, triples, etc. of pairwise orthogonal squares give more possibilities. – Aaron Meyerowitz Feb 5 '13 at 16:59
It's true that the lower bounds we get from (say) Latin squares are enormous, but they're probably a really long way from the truth. – Chris Godsil Feb 5 '13 at 18:30
As we know, every strongly regular graph over prime number of vertices is a conference graph and Paley graph is a conference graph and the following sentence due to Willem H. HAEMERS: For v = 5, 9, 13 and 17, the Paley graph is the only one with the given parameters. If $v \geq 25$, other graphs with the same parameters exist. in the following paper: Matrices for graphs, designs and codes Why this sentence is true? if this sentence is true, then there are at least 2 non-isomorphic strongly regular graphs on prime number of vertices $p>25$. – Mojtaba Jazaeri Feb 9 '13 at 18:52
Ted Spence determined all conference graphs on 29 vertices (see, there were 41 of them. I have not seen a proof that for any prime $p$ with $p\ge29$, there are at least two conference graphs on $p$ vertices. If you want to know what Haemers meant, you will have to ask him. – Chris Godsil Feb 9 '13 at 19:59

Your Answer


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.