Welcome to MathOverflow

Question

2

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

edited Feb 5 at 14:16

asked Feb 5 at 13:46

Mojtaba Jazaeri
33●3

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

Chris Godsil · Answer 1 · 2013-02-05 14:32:15Z UTC

3

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.

answered Feb 5 at 14:32

Chris Godsil
5,694●1●8●22

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 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 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 at 18:52

1

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. – Chris Godsil Feb 9 at 19:59

The number of non-isomorphic strongly regular graphs on n vertices

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.