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).

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.

$ gcc -Wall -O3 -funroll-loops -o gen_all_srgs_wqh_generic gen_all_srgs_wqh_generic.c $ cat ams 0111100010001000 1011010001000100 1101001000100010 1110000100010001 1000011110001000 0100101101000100 0010110100100010 0001111000010001 1000100001111000 0100010010110100 0010001011010010 0001000111100001 1000100010000111 0100010001001011 0010001000101101 0001000100011110 $ ./gen_all_srgs_wqh_generic 16 2 < ams | wc -l 2449 $ ./gen_all_srgs_wqh_generic 16 2 < ams | head -n 18 n=16 0100101110001000 1000011101000100 0001111000100010 0010110100010001 1011010010001000 0111100001000100 1110000100100010 1101001000010001 1000100001111000 0100010010110100 0010001011010010 0001000111100001 1000100010000111 0100010001001011 0010001000101101 0001000100011110 $ ./gen_all_srgs_wqh_generic 16 2 < ams \ | nauty-amtog -q | nauty-labelg -gqt | LC_ALL=C sort -u O^PLSgNacIk`UCGhAKW?~ OrqahoNqDGIPKS@k`L_?~

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.

$ cat ams ~??~}qtSqFktYRowXsiXeC?~^w?rNHYlO{rP`xhSliaX]WNBawX`[VTQkjHYYe_Nwm?LKtKsiiqiorJar_??^~|~_?F }Kro{phYlJTTBrKrLcW]XfchSlhZTIHdw]fEBowpo{wX`^g[`\TI|QsIqUeuUoe_Nwp~?w?srZKeRLIinTQaiorJ|KW JM^?[wBz_Nxe_U[pXrtTOilQitXXceZIXkcNFMNAw{?lJHLHsseuitAlJIsisrsA{YJpbde`wUN`WuMlHYQjhIiif`e WZX`kZFBKrKfKq[cyTJQilIiicrKNBM[KxMO_F~}?^w??^_????F~~~~w $ time nauty-showg -aq ams | tail -n +2 | ./gen_all_srgs_wqh_generic 63 2 > /dev/null real 0m0.610s user 0m0.608s sys 0m0.006s $ nauty-showg -aq ams | tail -n +2 | ./gen_all_srgs_wqh_generic 63 2 | nauty-amtog -q | wc -l 14175 $ nauty-showg -aq ams | tail -n +2 | ./gen_all_srgs_wqh_generic 63 2 \ > | nauty-amtog -q | nauty-labelg -gqt | LC_ALL=C sort -u | wc -l 2

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.

$ cat test_gr ~?@POGY_Gh@P_X@_eKOGtAOeOp?gPKaCUI?gQpC_I^qQPdAe~?H`?~CLbUrAK@XUOv@cnD_HciHk~]NL?S@XJH_JISJ HEhQORBCuGw_jBHWc[`weWIQ}sAIOOSbLPIAub@`dDpqGs`kCOuafOCdHqH{GHCfG`wPO_JSSEwDGIb`wWsB?rNyACP @PDJsUoAWGTZsCSoOO?????^~~m@PkS?rXoKYlSAd]CbdCKDLLHhB`eDX_hsmArB_XiSgb`kdAa@moCdFgHbyK_jlQu ?`[S[@?PNpoONHp?hf@UO^pG?Ig|A@kJDWca|?H@uIy_abNdAWH@yEacQqlM@aogW_qe}hQ?CIkg@bMBKSd`oKP?lD` eYEyCPo_CuYAx?UMOYG??Bb`uoBn?Nf@V?C^aVc\B@_WCM[]r_FMSAGKgpT`oaxIHoGc]cjOOeqHMAKoCVet?XOYRCO LPdgobJJ?MG[x?TwpOAvD?k?Yk_Cx`ggtcCOVoDPlEacDCEWQO{PwbcCPYEcCXG?xzKsBwA@`RGo????????~~~~~ $ nauty-countg --a -V -q test_gr Graph 1 : groupsize=3 $ nauty-showg -aq test_gr | tail -n +2 | ./gen_all_srgs_wqh_generic 81 3 \ > | nauty-amtog -q | nauty-labelg -gqt | wc -l 108 $ nauty-showg -aq test_gr | tail -n +2 | ./gen_all_srgs_wqh_generic 81 3 \ > | nauty-amtog -q | nauty-labelg -gqt | LC_ALL=C sort -u | wc -l 108

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.