9
$\begingroup$

Are there collections of already generated large strongly regular graphs available to download? By large I mean $n \geq 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, which contains a very nice list of srgs up to $n \leq 64$, but they are kind of on the small side. I also searched for software that can generate them but wasn't able to find one. (Although Brendan McKay's nauty software is extremely useful but doesn't seem to have an option to generate srgs). Note that all I'm looking for is few samples (not an exhaustive list which is probably not practical). Are there such sites or software available? Apologies if this does not qualify as a pure research question. Thank you!

$\endgroup$
8
$\begingroup$

Sage(math) aims to have graphs from A.Brouwer's web pages on s.r.g.'s available. Namely, at least one example for each case for which the existence is known. E.g. it will be possible to do things like

sage: t=graphs.strongly_regular_graph(126, 60, 33); t
complement(Taylor two-graph SRG): Graph on 126 vertices

The current beta version (6.9.beta4) has about 20% missing; after the work in progress here merged (hopefully in the forthcoming Sagemath 6.9) there will be at most 192 graphs missing.

Many of these graphs are actually available already in the current stable release of Sage, but there they aren't easy to find just from parameters.

$\endgroup$
  • $\begingroup$ Are they (you?) trying to implement entire families of constructions (most of which parameterised) or to produce specific graphs? $\endgroup$ – Gordon Royle Sep 3 '15 at 6:50
  • $\begingroup$ we implement infinite families, as well as "sporadic" examples. $\endgroup$ – Dima Pasechnik Sep 3 '15 at 16:22
  • $\begingroup$ Dima, thank you for the pointers! I didn't know about Sage and it definitely appears to have what I'm looking for. I'm going to download and start using it. $\endgroup$ – Jonathan HK Sep 3 '15 at 19:18
4
$\begingroup$

I am not aware of any such site.

To me, it even seems highly unlikely that anyone would try to produce such a list. For a start it would have be extremely selective - for example, there are 11,084,874,829 srgs on 57 vertices coming from Steiner triple systems on 19 points.

I (and collaborators) have used sage to construct srgs on up to something like 1000 vertices. This is not necessarily trivial (point graphs of flock generalized quadrangles say), but is certainly feasible.

If you gave some idea of what you want to do with these graphs, you might get a more useful response.

$\endgroup$
4
$\begingroup$

I have a program that makes SRG block-intersection graphs of Steiner Triple Systems, using the randomised hill-climbing method of Stinson and Mathon (?). It works in a fraction of a second on any size that is an integer of the form (v-1)v/6. I don't know if Sage has it (if not, it should).

$\endgroup$
  • $\begingroup$ Brendan, if you release its source under GPL, it will get into Sage... :-) $\endgroup$ – Dima Pasechnik Sep 3 '15 at 16:35
  • $\begingroup$ Hi Brendan, it would be really helpful if your program is added to nauty or released publicly under some license. Thanks! $\endgroup$ – Jonathan HK Sep 3 '15 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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