Many SRGs
Here I provide links to much of my collection of small SRGs in my Dropbox folder. See this preprint for details. The files are rather large and compressed with gzip. The format is graph6. Alternatively, you can use the C program below to generate (an adequate subset) of these graphs yourself.
SRGs
In the Preprint
- SRG(57, 24, 11, 9), 31,490,375 graphs, 3.1GB.
- SRG(63, 30, 13, 15), 13,505,292 graphs, 1.9GB.
- SRG(64, 21, 8, 6), 76,323 graphs, 5.9MB.
- SRG(64, 27, 10, 12), 8,613,977 graphs, 1.4GB.
- SRG(64, 28, 12, 12), 11,063,360 graphs, 1.5GB.
- SRG(70, 27, 12, 9), 78,900,835 graphs, 12GB.
- SRG(81, 24, 9, 6), 7,441,608 graphs, 1.3GB.
- SRG(81, 30, 9, 12), 3,770,759 graphs, 523MB.
- SRG(81, 32, 13, 12), 21,392,603 graphs, 4.4GB.
Bonus SRGs
More SRGs which where generated after the preprint was submitted. Note that I will move entries to the list above if the preprint includes them (due to revisions).
- SRG(81, 30, 9, 12), 16,565,438 graphs, 1.8GB, closed with respect to WQH switching with a partition of type 3,3,n-6.
- SRG(85, 20, 3, 5), 237,787 graphs, 59MB, WQH with 4,4,n-8, 5 steps, from the unique GQ(4, 4).
- SRG(96, 19, 2, 4), 178,040 graphs, 43MB, WQH with 4,4,n-8, 6 steps, from one of Haemer's graphs.
- SRG(96, 20, 4, 4), 133,005 graphs, 30MB, WQH with 4,4,n-8, 6 steps, from unique GQ(5,3).
Program for WQH Switching
Here a reasonably fast generic program for WQH switching to a graph of order n with a partition of type p,p,n-2p. You can find faster versions for the SRGs above, in the next section. This version is more user-friendly and written in better style.
I assume that the user is familiar with using the shell. Instructions and examples are for the Bourne Again Shell on a standard GNU/Linux system.
- Download gen_all_srgs_wqh_generic.c.
- Adjust defines in
gen_all_srgs_wqh_generic.c
if you know what you are doing. - Compile the file, for instance
gcc -O3 -funroll-loops -o gen_all_srgs_wqh_generic gen_all_srgs_wqh_generic.c
.
Usage: The first argument of gen_all_srgs_wqh_generic
is n,
the second one is p. If you did not change any defines, then n can be at most 448
and p can be at most 8. Output is "n=VTS" followed by a list of adjacency matrices.
Here is an example. The file ams
contains the adjacency matrix of the K4xK4 graph.
We find 2449 graphs via switching (which might be all isomorphic). Some of these are the Shrikande graph. Here we limit the output to the
adjacency matrices of the first two graphs found.
Now an example on how to use it in combination with nauty-traces' gtools.
The graph in ams
is Sp(6, 2) in graph6 format. Then we obsever that we 14175 graphs via WQH switching
with a partition of type 2,2,n-4. In the last command, we label these graphs canonically with Traces, remove duplicates, and observe that these 14175 graphs belong to one of two isomorphy classes.
One last example with a strongly regular graph on 81 vertices and a partition of type 3,3,n-6. This is more typical than the previous example as all produced cospectral graphs are pairwise non-isomorphic.
Actual C Source
The following provides code for GM switching with a partition of type 4,n-4 and WQH switching with a partition of type 3,3,n-6. For GM switching, there is a a second, faster version which works for up to 64 vertices if long is 64bit on your compiler/computer. This is all (at least slightly) optimized for my hardware. In general, the generic version above might be faster for you. The number of vertices is hardcoded as VTS. Adjust this value to your case, then compile. Input is a VTSxVTS adjacency matrix. Output is "n=VTS" followed by a list of adjacency matrices.