New directed strongly regular graphs on 60 vertices
Dean Crnković, Andrea Švob, Matea Zubović Žutolija · 2026
Read New directed strongly regular graphs on 60 vertices by Dean Crnković, Andrea Švob, Matea Zubović Žutolija (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-05884.txt.
Introduction
Crnkovic, Svob, and Zubovic Zutolija prove new directed strongly regular graphs on 60 vertices exist for six parameter sets, with degrees from 21 to 28. Each graph has 60 vertices, and the stated parameters fix valency plus intersection counts for the directed design. The group S5 times 2 moves every vertex to every other vertex in these graphs, so every vertex plays the same structural role.
Catalog record
| CREATOR | Dean Crnković, Andrea Švob, Matea Zubović Žutolija |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 9554 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.05884
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New directed strongly regular graphs on 60 vertices Dean Crnković, Andrea Švob, Matea Zubović Žutolija Abstract We prove the existence of directed strongly regular graphs with parameters (60,21,11,6,8), (60,22,12,8,8), (60,24,10,9,10), (60,25,17,8,12), (60,27,21,12,12) and (60,28,20,14,12). The group S 5 × 2 S_{5}\times 2 acts transitively on the constructed graphs. † † D. Crnković, A. Švob, M. Zubović Žutolija: Faculty of Mathematics, University of Rijeka, Radmile Matejčić 2, 51000 Rijeka, Croatia; e-mail : {deanc,asvob,matea.zubovic}@math.uniri.hr 2020 Mathematics Subject Classification: 05C20, 05B20, 05E30. Keywords: directed strongly regular graph, transitive group, symmetric group. 1 Introduction A directed strongly regular graph (dsrg) with parameters v,k,t,\lambda,\mu is a directed graph on v vertices, such that each vertex has indegree and outdegree k , and for any two vertices x,y the number of directed paths x\to z\to y is t , \lambda or \mu when x=y , or xy is an arc, or xy is not an arc, respectively. The digraphs that we use in this paper will not have more than one arc from one vertex to another, and further, will not have any arcs from a vertex to itself. Directed strongly regular graphs were introduced by Duval [ 5 ] , as a directed version of strongly regular graphs. According to the literature and the table in [ 3 ] , no directed strongly regular graphs with parameters (60,21,11,6,8), (60,22,12,8,8), (60,24,10,9,10), (60,25,17,8,12), (60,27,21,12,12) and (60,28,20,14,12) were known. In this note, we construct five nonisomorphic directed strongly regular graphs with parameters (60,21,11,6,8), 26 nonisomorphic directed strongly regular graphs with parameters (60,22,12,8,8), 32 nonisomorphic directed strongly regular graphs with parameters (60,24,10,9,10), four nonisomorphic directed strongly regular graphs with parameters (60,25,17,8,12), 24 nonisomorphic directed strongly regular graphs with parameters (60,27,21,12,12) and six nonisomorphic directed strongly regular graphs with parameters (60,28,20,14,12) that are the first known directed strongly regular graphs with these parameters. The computations in this paper are made by using programs written for Magma [ 1 ] . The directed strongly regular graphs constructed in this paper can be found at the link: https://www.math.uniri.hr/~asvob/DSRGs_v60.html 2 Construction of new directed strongly regular graphs We constructed the directed strongly regular graphs by using the method described in [ 4 , Theorem 3] . That construction produces simple 1-designs on which a group G acts transitively on the points and blocks. Hence, if the incidence structure of a 1-design obtained using [ 4 , Theorem 3] is the adjacency matrix of a directed strongly regular graph, then the graph admits a transitive action of G on the set of vertices. In this paper, we construct the directed strongly regular graphs using the group G=S_{5}\times 2 . 2.1 Construction of dsrg(60,28,20,14,12) The group S_{5}\times 2 has seven conjugacy classes of subgroups isomorphic to 2^{2} . Up to conjugation, there is exactly one subgroup H_{1} isomorphic to 2^{2} having the property that S_{5}\times 2 acts on cosets of H_{1} in 19 orbits. Using the method from [ 4 , Theorem 3] , by taking G=S_{5}\times 2 and the stabilizer of a vertex G_{\alpha}=H_{1} , we constructed two nonisomorphic dsrg(60,28,20,14,12) admitting a transitive action of the group S_{5}\times 2 , which we denote by \Delta_{1} and \Delta_{2} , where one digraph is obtained from the other by reversing the arcs. We say that the digraphs \Delta_{1} and \Delta_{2} are reverse to each other (see [ 2 , Section 3.4] ). The full automorphism group of the digraphs \Delta_{1} and \Delta_{2} is isomorphic to S_{5}\times 2 , and A_{5} acts regularly on the vertices of the digraphs. The group G has, up to conjugation, exactly one subgroup H_{2} isomorphic to 2^{2} having the property that S_{5}\times 2 acts on cosets of H_{2} in 32 orbits. Using the method from [ 4 , Theorem 3] , by taking G=S_{5}\times 2 and the stabilizer of a vertex G_{\alpha}=H_{2} , we constructed four nonisomorphic dsrg(60,28,20,14,12) admitting a transitive action of the group S_{5}\times 2 , which we denote by \Delta_{3} , \Delta_{4} , \Delta_{5} and \Delta_{6} . The digraph \Delta_{4} can be obtained by reversing the arcs of \Delta_{3} , and vice versa. The same holds for digraphs \Delta_{5} and \Delta_{6} . The full automorphism group of the digraphs \Delta_{3} and \Delta_{4} is isomorphic to S_{5}\times 2 , and A_{5} acts in two orbits on the vertices of the digraphs. The full automorphism group of the digraphs \Delta_{5} and \Delta_{6} is isomorphic to S_{5} , and A_{5} acts in two orbits on the vertices of the digraphs. The group G has, up to conjugation, two subgroups isomorphic to 2^{2} such that G acts on its cosets in 22 orbits. Let us denote these subgroups with H_{3} and H_{4} . We obtained another pair of directed strongly regular graphs with parameters (60,28,20,14,12), isomorphic to the ones denoted by \Delta_{3} and \Delta_{4} , by taking the subgroup H_{3} as the stabilizer of a vertex. The subgroup H_{4} produces two directed strongly regular graphs with parameters (60,28,20,14,12) that are isomorphic to \Delta_{3} and \Delta_{4} . 2.2 Construction of dsrg(60,22,12,8,8) By taking the subgroup H_{2} as the stabilizer of a vertex, we obtained 26 nonisomorphic dsrg(60,22,12,8,8) admitting a transitive action of the group S_{5}\times 2 , which we denote by \Delta_{7},\dots,\Delta_{32} . The full automorphism group of the digraphs \Delta_{17} , \Delta_{18} , \Delta_{19} and \Delta_{20} is isomorphic to S_{5}\times 2 , while the full automorphism group for the rest of the digraphs is isomorphic to S_{5} . The group A_{5} acts in two orbits on the vertices of the digraphs. Among these 26 nonisomorphic digraphs, there are 13 pairs of reversed digraphs. By taking any of the subgroups H_{3} or H_{4} as the stabilizer of a vertex, we obtained two pairs of pairwise reversed directed strongly regular graphs with parameters (60,22,12,8,8), isomorphic to digraphs \Delta_{17} , \Delta_{18} , \Delta_{19} and \Delta_{20} . 2.3 Construction of dsrg(60,25,17,8,12) By applying [ 4 , Theorem 3] to G=S_{5}\times 2 , taking the subgroup H_{2} as the stabilizer of a vertex, we also obtained two pairs of reversed directed strongly regular graphs with parameters (60,25,17,8,12), which we denote with \Delta_{33} and \Delta_{34} , and \Delta_{35} and \Delta_{36} . The full automorphism group of \Delta_{33} and \Delta_{34} is S_{5} , and the full automorphism group of digraphs \Delta_{35} and \Delta_{36} is G , and A_{5} acts on the vertices of these digraphs in two orbits. By applying [ 4 , Theorem 3] to G=S_{5}\times 2 , taking any of the subgroups H_{3} or H_{4} as the stabilizer of a vertex, we also obtained a pair of reversed directed strongly regular graphs with parameters (60,25,17,8,12), isomorphic to digraphs \Delta_{33} and \Delta_{34} . 2.4 Construction of dsrg(60,24,10,9,10) By taking the subgroup H_{2} as the stabilizer of a vertex, we obtained 32 nonisomorphic dsrg(60,24,10,9,10) admitting a transitive action of the group S_{5}\times 2 , which we denote by \Delta_{37},\dots,\Delta_{68} . The full automorphism group of the digraphs is isomorphic to S_{5} , and the group A_{5} acts in two orbits on the vertices of the digraphs. Among these 32 nonisomorphic digraphs, there are 16 pairs of reversed digraphs. 2.5 Construction of dsrg(60,27,21,12,12) By taking the subgroup H_{2} as the stabilizer of a vertex, we obtained 24 nonisomorphic dsrg(60,27,21,12,12) admitting a transitive action of the group S_{5}\times 2 , which