dot_clear dot_clear
Four different views of Glasgow University Tower

Strongly Regular Graphs on at most 64 vertices

Over the years I have been attempting to classify all strongly regular graphs with "few" vertices and have achieved some success in the area of complete classification in two cases that were previously unknown. These are (a) (29,14,6,7) and (b) (40,12,2,4). In the first of these, a non-exhaustive computer search by several authors unearthed 41 graphs, and this I managed to confirm as being the complete number (as did Frans Bussemaker in an independent search). It is perhaps interesting to point out that the complete search on a Pentium Pro 200 MHz now takes less that 12 hours! In case (b) an incomplete search had discovered 27 such graphs, but on returning to the problem I managed to complete the search, in the course of which one further graph was found. This is described in the paper [1].

As time permits I shall make these graphs available, along with others that I have on file. In the meantime, the two families referred to above can be obtained below as zero-one matrices.

There are four sets of parameters for strongly regular graphs on 36 vertices, two of which give rise to unique graphs. In the case of the other two, the exact numbers were not known at the time I wrote the paper [2]. There it was found that there are at least 32,548 srg's with parameters (36,15,6,6), at least 180 with parameters (36,21,12,12) and consequently the same number of complementary graphs (36,14,4,6). Recently Brendan McKay and I completed the search for all these strongly regular graphs and found that the lower bounds mentioned here are in fact also upper bounds. This follows from the fact that we found there are precisely 227 regular two-graphs on 36 vertices. This result has been written up and now appears in the Australasian Journal of Combinatorics [3]. For those interested I have included here a list of the 32,548 graphs with parameters (36-15-6-6) (4.5Mb) compressed using bzip2. Also, there are 3,854 descendants of the 227 regular two-graphs on 36 vertices. These are obtained by isolating a vertex by switching and then deleting it to get a strongly regular graph with parameters (35-18-9-9). These can be obtained either as a text file of (0,1) incidence matrices, below (4.64Mb), or its compressed form (35-18-9-9.bz2) (286Kb).

In a further classification, Willem Haemers and I have determined all SRG's(64,18,2,6) [4].

Finally, along with K. Coolsaet and J. Degraer [5], I have succeeded in completing the search for the (45,12,3,3) strongly regular graphs. There are precisely 78 of these and they are accessible via the table below.

5-2-0-1 9-4-1-2 10-3-0-1 13-6-2-3 15-6-1-3 16-5-0-2
16-6-2-2 17-8-3-4 21-10-3-6 25-8-3-2 25-12-5-6 26-10-3-4
27-10-1-5 28-12-6-4 29-14-6-7 35-18-9-9 36-10-4-2 36-14-4-6
36-14-7-4 40-12-2-4 45-12-3-3 49-12-5-2 50-21-8-9 64-18-2-6


[1] E Spence, The Strongly Regular (40,12,2,4) Graphs Elec. Journ. Combin. Vol 7(1) 2000.
[2] E Spence, Regular Two-Graphs on 36 Vertices, Lin.Alg. and its App., 226-228 (1995) 459-497.
[3] B McKay and E Spence,Classification of regular two-graphs on 36 and 38 vertices, Australasian Journal of Combinatorics, vol.24, p.293 (2001)
[4] W Haemers and E Spence, The Pseudo-Geometric Graphs for Generalised Quadrangles of Order (3,t), European J. Combin. 22 (2001), no. 6, 839-845
[5] Coolsaet K., J. Degraer, E. Spence, The Strongly Regular (45,12,3,3) graphs, Electronic Journal of Combinatorics, Vol 13(1), R32, 2006.