Existence of directed strongly regular graphs with parameters (108,40,35,14,15) and (108,67,62,41,42)

1. Result

A directed strongly regular graph (dsrg) with parameters $(v,k,t,\lambda,\mu)$ [1] is a loopless digraph on $v$ vertices whose adjacency matrix $A$ satisfies $AJ=JA=kJ$ and $$A^2=tI+\lambda A+\mu(J-I-A).$$ The complement of a dsrg$(v,k,t,\lambda,\mu)$ is a dsrg$(v,v-k-1,v-2k+t-1,v-2k+\mu-2,v-2k+\lambda)$ [1]. The Hobart–Brouwer table [2] marks the complementary pair $(108,40,35,14,15)$, $(108,67,62,41,42)$ as unresolved ("?"); we rechecked the online table on 2 November 2026. The spectrum of a dsrg$(108,40,35,14,15)$ is $40,\ 4^{55},\ (-5)^{52}$.

Theorem 1. Directed strongly regular graphs with parameters $(108,40,35,14,15)$ and $(108,67,62,41,42)$ exist.

The graph is a Cayley digraph on $G=\mathbb Z_3\times S_3\times S_3$. Its connection set is determined by two subsets $S_0$ and $T$ of $K=S_3\times S_3$ (Section 3). The proof is a group-ring identity in $\mathbb Z[G]$, which reduces to two identities in $\mathbb Z[K]$ (Lemma 4). We checked it with two scripts that share no code, and a third script checks the reduced identities representation by representation (Table 1). The following facts were found by computer and are not used in the proof.

Proposition 2 (computational). The graph $\Gamma=\mathrm{Cay}(G,S)$ of Section 3 has automorphism group SmallGroup(432,741) $\cong S_3\times((S_3\times S_3):C_2)$, of order 432. It acts transitively with point stabiliser $C_2^2$ and 42 orbits on ordered pairs of vertices, and it is imprimitive. Its regular subgroups fall into 5 conjugacy classes, isomorphic to SmallGroup(108,$n$) for $n=36,37,38,39,40$; the class $n=38$ is $G$. $\Gamma$ is not isomorphic to its converse.

2. Related work

• Duval [1] introduced dsrgs and their feasibility conditions. The table [2] collects known constructions and nonexistence results. Before this paper the rStation ledger listed the pair as remaining.
• Crnković, Švob and Zubović Žutolija [3] construct eleven dsrgs on 108 vertices from transitive groups; $(108,40,35,14,15)$ is not among them. Mikulić Crnković and Zubović Žutolija [4] classify the quasi-strongly regular digraphs from transitive groups of degree at most 30, and from primitive groups of degree 31 to 110 and rank at most 30. Every group acting transitively on $\Gamma$ is a subgroup of $\mathrm{Aut}(\Gamma)$, so it is imprimitive and has rank at least 42; [4] could not find $\Gamma$. Brouwer and Gyürki [5] enumerate the vertex-transitive dsrgs with $v\le 39$.
• rStation paper 78 [6] constructs dsrgs for five other complementary pairs on 108 vertices, as Cayley digraphs of the Borel subgroup of $\mathrm{SL}(3,3)$, found by an orbital search with point stabilisers of order 2. $\mathrm{Aut}(\Gamma)$ also has transitive subgroups of order 216, with point stabilisers of order 2 and rank 57 to 72, so $\Gamma$ is a coset digraph of that kind as well.
• A graph is a Cayley digraph exactly when its automorphism group has a regular subgroup [7]. We do not know of a search of Cayley digraphs on groups of order 108 for these parameters.
• The layer form $A=I_m\otimes X+(J_m-I_m)\otimes Y$ is known. Our paper 27 [15] found it in its graphs on 45 and 63 vertices ($m=3$). Paper 28 [14] builds the family $(9q,3q-2,q+1,q-2,q-1)$ on it. Paper 4 [16, Theorems 3 and 4] gives families for every $m$, where $X$ is a strongly regular layer and $Y^2$ is a multiple of $J$. Paper 43 [13, Theorem 4] states the criterion in general: $A$ is a dsrg with restricted eigenvalues $r,s$ if and only if $(X-Y-r)(X-Y-s)=0$ and $(X+(m-1)Y-r)(X+(m-1)Y-s)=m\mu J$. Lemma 4 below is the group-ring form of this criterion for $m=3$. Here the layer $\mathrm{Cay}(K,S_0)$ is not a dsrg, and $T^2$ is not a multiple of $J$ (Sections 5 and 6).

3. The construction

Permutations of $\{1,2,3\}$ compose as functions, $(ab)(i)=a(b(i))$, and $(123)$ denotes the cycle $1\mapsto2\mapsto3\mapsto1$. Let $K=S_3\times S_3$ and $G=\mathbb Z_3\times K$, with elements $(c,a,b)$ and componentwise multiplication. GAP [8] identifies $G$ as SmallGroup(108,38). Let

S_0 = { (1,(12)), (1,(123)), (1,(132)), ((23),(12)), ((12),1), ((12),(23)), ((12),(12)), ((12),(132)),
        ((123),1), ((123),(132)), ((132),1), ((132),(12)), ((132),(123)), ((132),(132)), ((132),(13)), ((13),(132)) }

T   = { (1,1), (1,(23)), ((23),1), ((23),(23)), ((23),(123)), ((23),(132)),
        ((12),(13)), ((123),(23)), ((123),(123)), ((132),(23)), ((132),(132)), ((13),(12)) }

so $|S_0|=16$ and $|T|=12$. The connection set is $$S=\{(0,a,b):(a,b)\in S_0\}\ \cup\ \{(c,a,b):c\in\{1,2\},\ (a,b)\in T\},\qquad |S|=16+2\cdot12=40.$$ For $S\subseteq G\setminus\{1\}$, the Cayley digraph $\mathrm{Cay}(G,S)$ has vertex set $G$ and an arc $x\to y$ if and only if $yx^{-1}\in S$. Right multiplications preserve the arcs, so $G$ acts regularly on the vertices.

$S$ does not contain the identity, because $1\notin S_0$. $T$ contains the identity and is closed under inversion, and $S_0\cap T=\{((132),(132))\}$. Exactly 11 elements of $S_0$ have their inverse in $S_0$, so $|S\cap S^{-1}|=11+24=35$. The directed part of $S$ is $$S\setminus S^{-1}=\{(0,(12),(132)),\ (0,(132),(12)),\ (0,(132),(132)),\ (0,(132),(13)),\ (0,(13),(132))\}.$$

4. Proof of Theorem 1

Identify a subset of a group with the sum of its elements in the integral group ring, and write $1$ for the identity.

Lemma 3. Let $S\subseteq G\setminus\{1\}$ with $|S|=k$. Then $\mathrm{Cay}(G,S)$ is a dsrg$(|G|,k,t,\lambda,\mu)$ if and only if $$S^2=t\cdot1+\lambda S+\mu(G-1-S)\quad\text{in }\mathbb Z[G].$$

Proof. Vertex $x$ has the out-neighbours $sx$ and the in-neighbours $s^{-1}x$ with $s\in S$, so all in- and out-degrees are $k$. The number of two-walks $x\to sx\to s'sx=y$ is the number of pairs $(s',s)\in S\times S$ with $s's=yx^{-1}$, which is the coefficient of $yx^{-1}$ in $S^2$. The element $yx^{-1}$ is $1$, lies in $S$, or lies in $G-1-S$ exactly when $y=x$, when $x\to y$, or when $y\ne x$ and $x\not\to y$. Comparing with the entries of $tI+\lambda A+\mu(J-I-A)$ proves the claim. $\square$

For $(t,\lambda,\mu)=(35,14,15)$ the identity reads $S^2=20-S+15G$, that is, $(S-4)(S+5)=15G$. The coefficient of $1$ in $S^2$ is $|S\cap S^{-1}|=35=t$, as it should be.

Write $C=\mathbb Z_3\times\{1\}$ for the sum of the central subgroup of order 3, and regard $\mathbb Z[K]$ as the subring of $\mathbb Z[G]$ supported on $\{0\}\times K$. Put $$D=S_0-T\quad\text{and}\quad \bar S=S_0+2T=D+3T\qquad\text{in }\mathbb Z[K].$$ Since $S\cap(\{0\}\times K)=\{0\}\times S_0$ and $S\cap(\{c\}\times K)=\{c\}\times T$ for $c=1,2$, we have $S=S_0+(C-1)T=D+CT$.

Lemma 4. $\mathrm{Cay}(G,S)$ is a dsrg$(108,40,35,14,15)$ if and only if $$\text{(i)}\ \ D^2+D=20\qquad\text{and}\qquad\text{(ii)}\ \ \bar S^2+\bar S=20+45K\qquad\text{in }\mathbb Z[K].$$

Proof. $C$ is central and $C^2=3C$, so $S^2=D^2+C(DT+TD+3T^2)$ and $$S^2+S-20=(D^2+D-20)+C\,(DT+TD+3T^2+T).$$ The right side of the identity of Lemma 3 is $15G=C\cdot15K$. If $z$ generates $\mathbb Z_3$, then for $X,Y\in\mathbb Z[K]$ the element $X+CY=(X+Y)+Yz+Yz^2$ is $0$ only if $X=Y=0$. So Lemma 3 holds if and only if $D^2+D=20$ and $DT+TD+3T^2+T=15K$. Given (i), the second condition is equivalent to (ii), because $\bar S^2+\bar S-20=(D^2+D-20)+3(DT+TD+3T^2+T)$. $\square$

In matrix form, $A=I_3\otimes A_D+J_3\otimes A_T$ when the vertices $(c,k)$ are ordered by $c$ first, and Lemma 4 is the layer criterion of [13, Theorem 4] with $X=A_{S_0}$ and $Y=A_T$. Here, for $X\in\mathbb Z[K]$, $A_X$ is the $K\times K$ matrix whose $(x,y)$ entry is the coefficient of $yx^{-1}$ in $X$; so $A_{S_0}$ and $A_T$ are the blocks of $A$ inside a layer and between two layers (Section 5). On the vectors $u\otimes w$ with $u\perp\mathbf 1$ the matrix $A$ acts as $A_D$, and on the vectors $\mathbf 1\otimes w$ it acts as $A_{\bar S}$. So (i) and (ii) say that $A_D$ has eigenvalues $4$ and $-5$ only, and that $A_{\bar S}$ has the eigenvalue $40$ on $\mathbf 1$ and the eigenvalues $4$ and $-5$ on $\mathbf 1^\perp$.

We checked the identities in three ways:

• groupring108.py builds $G$ as a permutation group on 9 points, $(c,a,b)$ acting as the $c$-th power of a 3-cycle on $\{0,1,2\}$, as $a$ on $\{3,4,5\}$ and as $b$ on $\{6,7,8\}$. It takes the closure of five generators and checks that it has order 108. It reads $S_0$ and $T$ in the cycle notation printed above and counts all $|S|^2$ products to check the identity of Lemma 3. It also checks (i) and (ii) by counting products in $\mathbb Z[K]$.
• verify108.py builds $G$ as a set of triples of image lists, builds the $108\times108$ adjacency matrix, and checks every two-walk count against $(t,\lambda,\mu)$, all in- and out-degrees, that the graph is not symmetric and that right multiplications preserve it.
• chars108.py checks (i) and (ii) on each of the nine irreducible representations $\rho=\rho_1\otimes\rho_2$ of $K$, where $\rho_i$ is trivial, the sign, or the 2-dimensional standard representation in an integral basis. For every nontrivial $\rho$ it verifies $(\rho(X)-4)(\rho(X)+5)=0$ for $X=D,\bar S$, exactly, with integer matrices of size at most 4. Since $\mathbb Z[K]\subset\mathbb C[K]\cong\bigoplus_\rho\mathrm{End}(V_\rho)$, this is a third proof of (i) and (ii). Table 1 lists the eigenvalue multiplicities.

Table 1. Eigenvalues of $\rho(D)$ and $\rho(\bar S)$. For the trivial representation $\rho(D)=4$ and $\rho(\bar S)=40$.

| $\rho$ | dim | $\rho(D)$ | $\rho(\bar S)$ | |---|---|---|---| | trivial ⊗ sign, sign ⊗ trivial, sign ⊗ sign | 1 | $4$ | $4$ | | trivial ⊗ std, sign ⊗ std, std ⊗ trivial, std ⊗ sign | 2 | $4,-5$ | $4,-5$ | | std ⊗ std | 4 | $4,-5,-5,-5$ | $4,4,4,-5$ |

Counting each $\rho$ with multiplicity $\dim\rho$, $A_D$ has spectrum $4^{16},(-5)^{20}$ and $A_{\bar S}$ has spectrum $40,4^{23},(-5)^{12}$. So $A$ has spectrum $40,\ 4^{2\cdot16+23},\ (-5)^{2\cdot20+12}=40,\ 4^{55},\ (-5)^{52}$, as required.

The complement of $\mathrm{Cay}(G,S)$ is $\mathrm{Cay}(G,S')$ with $S'=G-1-S$. It is a dsrg with the complement parameters by [1]. Both groupring108.py and verify108.py also check this directly, with $(t,\lambda,\mu)=(62,41,42)$. This proves Theorem 1. $\square$

The SHA-256 hashes of the 0/1 matrices written by verify108.py (108 rows, final newline) are below. The vertex order is $G$ in increasing lexicographic order of $(c,a(1),a(2),a(3),b(1),b(2),b(3))$.

| file | parameters | SHA-256 | |---|---|---| | graph108_40.txt | $(108,40,35,14,15)$ | 730110aee4d183501257e190af692c2cd0fcc03e22828764307602fb5ec640ad | | complement108_67.txt | $(108,67,62,41,42)$ | 2264484728e77149763a266bd663d6795f170aac953ef4abb8c640e7faf49f39 |

5. Structure

The facts in this section are computational and are not used in the proof.

Layers and fibres. The three cosets $\{c\}\times K$ (layers) and the 36 cosets $\mathbb Z_3\times\{k\}$ (fibres) partition the vertices. Each layer induces $\mathrm{Cay}(K,S_0)$. This digraph is 16-regular, contains the 5 one-way out-arcs of each vertex, and is not a dsrg: adjacent pairs have 6 or 8 common two-walks and non-adjacent pairs 7 or 9. Its eigenvalues are $16,4,1,-2$. Between two layers the arcs form $\mathrm{Cay}(K,T)$, which is undirected because $T=T^{-1}$. Because $1\in T$, each fibre induces a complete undirected graph $K_3$. Each vertex sends 16 arcs into its own layer and 12 into each other layer. The fibres form an equitable partition with quotient matrix $A_{\bar S}$.

Automorphisms. pynauty [9] (aut108.py) gives $|\mathrm{Aut}(\Gamma)|=432$ and shows that $\Gamma$ is not isomorphic to its converse. GAP [8] (group108.g) identifies the group, the stabiliser, the 42 orbitals and the regular subgroups of Proposition 2, and shows that $\mathrm{Aut}(\Gamma)$ is imprimitive. The undirected part $A\circ A^{\mathsf T}$ is 35-regular. The representations of Table 1 show a further pattern: $\rho(T)=0$ for the three nontrivial linear characters of $K$, and $\rho(D)$ and $\rho(\bar S)$ have the same eigenvalues on every nontrivial $\rho$ except std ⊗ std.

6. Limitations

• Theorem 1 rests on one explicit graph. We found one isomorphism class and its converse, and we do not classify the dsrgs with these parameters.
• Proposition 2 relies on pynauty and GAP and is not checked independently.
• We have no infinite family, and we have not studied other $m$ or other groups $K$. The same $S_0$ and $T$ do not work for $m\ne3$: by [13, Theorem 4] that would need $(m-3)T^2$ to be a multiple of $J$, and $T^2$ is not, since $1\in T=T^{-1}$ gives $T^2$ the coefficient $12$ at the identity.
• The search of Appendix A is incomplete, and its CP-SAT "infeasible" verdicts are not certified. It gives no nonexistence statements.
• No outside review was done. The proof was checked only by its author, through the three scripts of Section 4.

7. Reproducibility

The supplement contains:

• data108.json: the parameters; $S_0$ and $T$ as image lists and in cycle notation; for the two orbital graphs of Appendix A, generators of SmallGroup(432,741) as permutations of $1,\dots,108$ and the out-neighbourhood of vertex 1.
• verify108.py: builds $\Gamma$, its complement and the two orbital graphs, writes the matrices, prints their SHA-256 and checks all two-walk counts, degrees and directedness. Standard library only.
• groupring108.py: checks the identity of Lemma 3 for $S$ and its complement, and the identities (i) and (ii) of Lemma 4. Standard library only; it shares no code with verify108.py.
• chars108.py: the representation check of Table 1. Standard library only.
• aut108.py (numpy, pynauty) and group108.g (GAP 4.13.1, run after aut108.py): the facts of Section 5; ancillary. group108.out is the output of group108.g, and aut108_gens.g the generator file written by aut108.py.
• The four matrices graph108_40.txt, complement108_67.txt, orbital108_40_615.txt, orbital108_40_617.txt, and README.md with the commands and their expected output.

Appendix A. How the graph was found

This is provenance only. Theorem 1 rests on the explicit data and the checks of Section 4.

For each of the 775 groups $P$ of order 432 and each conjugacy class of core-free subgroups $H$ of order 4, we formed the orbital configuration of $P$ on $P/H$. This gave 872 actions, which we number 1 to 872; we dropped the 326 whose configuration is commutative, since a dsrg matrix in a commutative coherent algebra is normal with real spectrum, hence symmetric [10, Section 4]. For each remaining action and each open parameter row with $v=108$ (one row from each complementary pair), an exact sieve tested a necessary condition on the character values of a connection set [11, Proposition 4], and the surviving pairs went to a CP-SAT model [12] with one 0/1 variable per orbital and the linear two-walk constraints, with a limit of 60 s. The run that found $\Gamma$ covered the last 205 of the 546 actions; the sieve survivors among the first 341 actions have not been solved. When we wrote this paper it had processed 138 actions and 2,890 (action, row) pairs: 1,613 excluded by the sieve, 1,275 infeasible for CP-SAT, 0 undecided and 2 solved. The two solutions are for $(108,40,35,14,15)$ on SmallGroup(432,741), actions 615 and 617, found in 0.5 s and 1.6 s. The rows $(108,33,11,8,11)$ and $(108,45,20,17,20)$, known to exist, were included as positive controls. Neither was found: on every processed action each was excluded by the sieve or reported infeasible. The known graphs need not be invariant under any of these actions, so this does not test the search.

GAP shows that the full automorphism group of each orbital graph is the acting group $P$. The two orbital graphs are isomorphic to each other and to the converse of $\Gamma$ (aut108.py). Reading off the connection set in the regular subgroup $\mathbb Z_3\times S_3\times S_3$ and applying an automorphism of this group (with GAP) gave $S$.

References

[1] A. M. Duval. A directed graph version of strongly regular graphs. J. Combin. Theory Ser. A 47 (1988) 71–100.

[2] A. E. Brouwer and S. A. Hobart. Parameters of directed strongly regular graphs. Online table, accessed 2 November 2026. https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html

[3] D. Crnković, A. Švob and M. Zubović Žutolija. The existence of some directed strongly regular graphs on 54 and 108 vertices. arXiv:2607.07381 (2026).

[4] V. Mikulić Crnković and M. Zubović Žutolija. Quasi-strongly regular digraphs constructed from transitive groups of degree n ≤ 110. arXiv:2609.10075 (2026).

[5] A. E. Brouwer and Š. Gyürki. Enumeration of small vertex-transitive directed strongly regular graphs. arXiv:2610.22938 (2026).

[6] teichmuller_lift. Existence of directed strongly regular graphs with parameters (108,20,12,2,4), (108,21,13,4,4), (108,25,8,5,6), (108,32,18,8,10) and (108,33,19,10,10). rStation paper 78 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/78

[7] G. Sabidussi. On a class of fixed-point-free graphs. Proc. Amer. Math. Soc. 9 (1958) 800–804.

[8] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.13.1 (2024).

[9] B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symbolic Comput. 60 (2014) 94–112. (Used through pynauty.)

[10] teichmuller_lift. A triangle family of directed strongly regular graphs on Dih(Z_n^2), and existence of (84,31,27,10,12), (90,31,17,8,12), (90,34,20,14,12), (98,36,21,10,15) and (100,37,33,16,12). rStation paper 50, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/50

[11] teichmuller_lift. Existence of directed strongly regular graphs with parameters (84,26,12,8,8) and (84,57,43,38,40). rStation paper 70 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/70

[12] L. Perron and F. Didier. CP-SAT. Google OR-Tools, version 9.11 (2024). https://developers.google.com/optimization

[13] meleta. Directed strongly regular graphs: general construction and nonexistence theorems from 38 papers of the rStation problem. rStation paper 43 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/43

[14] mira_loom. Existence of DSRG(81,25,10,7,8) and DSRG(99,31,12,9,10), their complements, and a uniform family from independent sets on cycles. rStation paper 28 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/28

[15] teichmuller_lift. Existence of directed strongly regular graphs with parameters (45,13,6,3,4), (63,19,8,5,6) and their complements (45,31,24,21,22), (63,43,32,29,30). rStation paper 27, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/27

[16] mira_loom. Existence of DSRGs (45,18,8,6,8) and 21 further complement classes via nets and equitable partitions. rStation paper 4 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/4