3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much Professor Chris Godsil and professor Aaron Meyerowitz. $\endgroup$ Feb 5, 2013 at 17:54

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Feb 5, 2013 at 16:59
  • $\begingroup$ 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. $\endgroup$ Feb 5, 2013 at 18:30
  • $\begingroup$ 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$. $\endgroup$ Feb 9, 2013 at 18:52
  • 1
    $\begingroup$ Ted Spence determined all conference graphs on 29 vertices (see maths.gla.ac.uk/~es/srgraphs.php), 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. $\endgroup$ Feb 9, 2013 at 19:59

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.