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 these graphs yourself.

SRGs

Graphs in the Accepted Paper

  1. SRG(57, 24, 11, 9), 31,490,375 graphs, GM with 4,n-4, 9 steps, from some S(2, 3, 19), 3.1G.
  2. SRG(63, 30, 13, 15), 13,505,292 graphs, GM with 4,n-4, 5 steps, from Sp(6, 2), 1.9G.
  3. SRG(64, 21, 8, 6), 76,323 graphs, GM with 4,n-4, infinite steps, from Bilin(2, 3, 2), 5.9M.
  4. SRG(64, 27, 10, 12), 8,613,977 graphs, GM with 4,n-4, 5 steps, from VO-(6, 2), 1.4G.
  5. SRG(64, 28, 12, 12), 11,063,360 graphs, GM with n,n-4, 5 steps, from VO+(6, 2), 1.5G.
  6. SRG(70, 27, 12, 9), 78,900,835 graphs, GM with 4,n-4, 5 steps, from some S(2, 3, 21), 12G.
  7. SRG(81, 24, 9, 6), 7,441,608 graphs, WQH with 3,3,n-6, 6 steps, from VNO+(4, 3), 1.3G.
  8. SRG(81, 30, 9, 12), 16,565,438 graphs, WQH with 3,3,n-6, infinite steps, from VNO-(4, 3), 1.8G.
  9. SRG(81, 32, 13, 12), 21,392,603 graphs, WQH with 3,3,n-6, 6 steps, from Bilin(2, 2, 3), 4.4G.
  10. SRG(85, 20, 3, 5), 237,787 graphs, WQH with 4,4,n-8, 5 steps, from the unique GQ(4, 4), from Sp(4, 4), 59M.
  11. SRG(96, 19, 2, 4), 178,040 graphs, WQH with 4,4,n-8, 6 steps, from one of Haemers' graphs, from some Haemers(4), 43M.
  12. SRG(96, 20, 4, 4), 133,005 graphs, WQH with 4,4,n-8, 6 steps, from unique GQ(5,3), from NO+(8, 2), 30M.

Bonus Graphs

If I generate more SRGs using WQH switching, then they will go here.

  1. SRG(85, 20, 3, 5), 3,565,042 graphs, WQH with 4,4,n-8, 6 steps, from unique GQ(4, 4), from Sp(4, 4), 785M.
  2. SRG(120, 63, 30, 36), 4,708,637 graphs, GM with 4,n-4, 4 steps, from NO+(8,2), 2.8G.

The 4-Vertex Condition

For a different preprint with Brouwer and Kantor on the 4-vertex condition, I generated many strongly regular graphs satisfying the 4-vertex condition. Here are some. The enumeration should be complete for all given cases (using this particular method).

  1. 4-vc SRG(63, 30, 13, 15), 281 graphs, 92K, subset of the 13,505,292 graphs above.
  2. 4-vc SRG(255, 126, 61, 63), 3,374 graphs, 18M, Kantor switching with Sp(8, 2) and point-hyperplane design.
  3. 4-vc SRG(255, 126, 61, 63), 113,519 graphs, 79M, Kantor switching with Sp(8, 2) and 2-(15, 7, 3) design 3+12,3+12.
  4. 4-vc SRG(255, 126, 61, 63), 340,730 graphs, 288M, Kantor switching with Sp(8, 2) and 2-(15, 7, 3) design 7+8,1+14.
  5. 4-vc SRG(255, 126, 61, 63), 328,078 graphs, 275M, Kantor switching with Sp(8, 2) and 2-(15, 7, 3) design 1+14,7+8.
  6. 4-vc SRG(255, 126, 61, 63), 677,460 graphs, 580M, Kantor switching with Sp(8, 2) and 2-(15, 7, 3) design 1+6+8,1+6+8.
  7. 4-vc SRG(364, 120, 38, 40), 252 graphs, 2.7M, Kantor switching with Sp(6, 3).
  8. SRG(364, 120, 38, 40), 252 graphs, 2.7M, Kantor switching with O(6, 3), 4 graphs satisfy the 4-vertex condition.

More Kantor-type Switching

Van Dam and Guo describe a variant of Kantor switching in this preprint for symplectic generalized quadrangles. As in Subsection 7.2 of my preprint with Brouwer and Kantor, one can enumerate them using double cosets. (This is not mentioned in van-Dam-Guo.) As I could reuse my code from that paper, here is a complete enumeration for small cases using classical affine planes.

  1. SRG(40, 12, 2, 4), 9 graphs, 4K, Kantor switching with Sp(4, 3) and the unique affine plane of order 3.
  2. SRG(85, 20, 3, 5), 632,026 graphs, 80M, Kantor switching with Sp(4, 4) and the unique affine plane of order 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.

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.

  1. Download gen_all_srgs_wqh_generic.c.
  2. Adjust defines in gen_all_srgs_wqh_generic.c if you know what you are doing.
  3. 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 more specialized 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.

  1. gen_all_srgs.c
  2. gen_all_srgs_64vts.c
  3. gen_all_srgs_wqh6.c

Universiteit Gent and Vakgroep Wiskunde: Analyse, Logica en Discrete Wiskunde.

Hebrew University of Jerusalem and Einstein Institute.

University of Regina and Department of Mathematics and Statistics.

Justus-Liebig-Universität Gießen and Mathematisches Institut.