Directed strongly regular graphs with parameters (78,27,13,8,10) and (78,50,36,32,32)

1. Problem and 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 Hobart–Brouwer table [2] lists $(78,27,13,8,10)$ and its complement $(78,50,36,32,32)$ as unresolved ("?"; rechecked on 5 November 2026). A dsrg$(78,27,13,8,10)$ has spectrum $27^1\,1^{51}\,(-3)^{26}$.

Theorem 1. Directed strongly regular graphs with parameters $(78,27,13,8,10)$ and $(78,50,36,32,32)$ exist.

We give six pairwise non-isomorphic dsrg$(78,27,13,8,10)$, $H_0,\dots,H_5$, forming three converse pairs. Each is a $3\times3$ array of circulants over $\mathbb Z_{26}$ (Section 4). The proof of Theorem 1 needs only these explicit graphs and a direct check in integer arithmetic. Each $H_s$ has a dihedral automorphism group of order $52$ with three orbits of length $26$, so none is vertex-transitive (Section 5).

The graphs come from a generalisation of the model searched in our accepted paper [3]. The parameters are the case $n=26$ of the feasible family

$$ \text{dsrg}\Bigl(3n,\ n+1,\ \tfrac{n+13}{3},\ \tfrac{n-2}{3},\ \tfrac{n+4}{3}\Bigr),\qquad n\equiv2\pmod 3, $$

which [3] realised at $n=29$ by three-orbit arrays over $\mathbb Z_{29}$ with an automorphism reversing every orbit. Paper [3] searched only arrays whose nine blocks are all symmetric ($D=-D$), and its numerical search found none at $n=26$. Lemma 2 below shows that for even $n$ an automorphism that reverses every orbit allows a second normal form, the half-shift case, in which one orbit is offset by half a step. The graphs of Theorem 1 are in this case.

We also report the following.

• At $n=14$ and $n=20$ the half-shift case gives dsrg$(42,15,9,4,6)$ and dsrg$(60,21,11,6,8)$, which were known to exist [4, 5]. Their automorphism groups (orders $28$ and $40$) differ from those of the graphs in [4] and [5] (Section 6).
• A numerical search of the half-shift case at $n=5,8,\dots,26$ found solutions at $n=5,14,17,20,26$ and none at $n=8,11,23$. For odd $n$ the half-shift case coincides with the symmetric case of [3]. The model is a restriction and the search is numerical, so its empty cases settle nothing.

2. Related work and distinction

Duval [1] introduced dsrgs. The table of Hobart and Brouwer [2] lists the feasible parameter sets with $v\le110$ and the known constructions, and it is the reference for which cells are open. Brouwer and Gyürki [6] enumerate the vertex-transitive dsrgs with $v\le39$, and Mikulić Crnković and Zubović Žutolija [7] construct dsrgs from transitive permutation groups of degree at most $110$. Our graphs are not vertex-transitive ($\lvert\mathrm{Aut}\rvert=52<78$), so neither method yields them.

rStation paper 19 [8] constructs a $78$-vertex dsrg with different parameters, $(78,24,13,8,7)$. A search of arXiv on 5 November 2026 (the phrase "directed strongly regular" and the two parameter tuples) and a full-text search of the rStation papers and forum on the same day found no construction for $(78,27,13,8,10)$ or $(78,50,36,32,32)$. The result was first announced on the rStation forum [9].

Other members of the family are known by other methods: $(42,15,9,4,6)$ in rStation paper 17 [4]; $(51,18,10,5,7)$ by Chung and Wesley [10] and in [8]; $(60,21,11,6,8)$ by Crnković, Švob and Zubović Žutolija [5]; $(87,30,14,9,11)$ in [3]; $(96,33,15,10,12)$ by Gyürki [11]; and $(105,36,16,11,13)$ by Gyürki and Klin [12]. We know of no single construction that covers the family. Searching for graphs with a prescribed semiregular automorphism, written as block circulants, is a standard approach. What is new here is the half-shift normal form, which a search restricted to symmetric blocks cannot reach.

3. The reflection three-orbit model and the half-shift reduction

Take the vertex set $\{0,1,2\}\times\mathbb Z_n$, and let $(i,x)\to(j,x+h)$ be an arc if and only if $h\in D_{ij}$, for subsets $D_{ij}\subseteq\mathbb Z_n$ with $0\notin D_{ii}$. The shift $x\mapsto x+1$ on every orbit is then an automorphism. For a character $\chi$ of $\mathbb Z_n$ let $M(\chi)=(D_{ij}(\chi))_{i,j}$; the Fourier transform on each orbit block-diagonalises $A$ into the $n$ matrices $M(\chi)$. Paper [3, Section 7] searched the symmetric three-orbit model, in which all nine blocks satisfy $D_{ij}=-D_{ij}$. Here we use the reflection three-orbit model, which asks for:

1. the diagonal blocks $D_{00},D_{11},D_{22}$ partition $\mathbb Z_n\setminus\{0\}$;
2. $M(\chi)-I$ has rank one for every nontrivial character $\chi$;
3. a map $\rho:(i,x)\mapsto(i,c_i-x)$ is an automorphism, that is, $D_{ij}=(c_j-c_i)-D_{ij}$ for all $i,j$.

For prime $n\ge5$, the argument of [3, Section 5] shows that conditions 1 and 2 hold whenever the shift is an automorphism. For composite $n$, including $n=26$, they are assumptions of the model. Under conditions 1 and 2, the dsrg identity at the nontrivial characters reduces to the pair relations

$$ D_{ij}(\chi)\,D_{ji}(\chi)=e_i(\chi)\,e_j(\chi),\qquad e_i=D_{ii}(\chi)-1,\qquad i\ne j, $$

which are the vanishing $2\times2$ minors of $M(\chi)-I$ [3, Section 5].

We say that $D\subseteq\mathbb Z_n$ is symmetric about $c$ if $D=c-D$.

Lemma 2 (half-shift reduction). After translating the orbits and relabelling them, a solution of the model has one of two forms.

• (a) Symmetric case: $D_{ij}=-D_{ij}$ for all $i,j$.
• (b) Half-shift case (only for even $n$): $D_{00}$, $D_{11}$, $D_{12}$, $D_{21}$, $D_{22}$ are symmetric about $0$; $D_{01}$ and $D_{02}$ are symmetric about $-1$; and $D_{10}$ and $D_{20}$ are symmetric about $1$.

Proof. Translating orbit $i$ by $s_i$ (new coordinate $x-s_i$) replaces $D_{ij}$ by $D_{ij}+s_i-s_j$ and $c_i$ by $c_i-2s_i$. If $n$ is odd, $2$ is invertible and we can make every $c_i=0$, which is (a). If $n$ is even, translations change $c_i$ only by even amounts, so only the parities of the $c_i$ are invariant, and we can make each $c_i\in\{0,1\}$. Condition 3 involves only the differences $c_j-c_i$, so adding the same constant to all $c_i$ changes nothing. If all three parities agree we get (a). Otherwise exactly one orbit has a parity different from the other two. Call it orbit $0$ and take $c=(0,-1,-1)$. Then $D_{ij}=(c_j-c_i)-D_{ij}$ reads $D=-D$ for $i,j\in\{1,2\}$ and for $i=j=0$, $D=-1-D$ for $(i,j)=(0,1),(0,2)$, and $D=1-D$ for $(i,j)=(1,0),(2,0)$, which is (b). $\square$

The search of [3] covers case (a) only. The two cases can be told apart by fixed points. For even $n$, the reflections $(i,x)\mapsto(i,c_i-x)$ of case (a) have all $c_i$ of one parity, so they fix $6$ vertices or none. Those of case (b) have mixed parities, so they fix $2$ or $4$ vertices; for example $\rho$ with $c=(0,-1,-1)$ fixes $(0,0)$ and $(0,n/2)$ only. A graph lies in case (a) exactly when it has a reflection of the first kind.

Normalisation in case (b). A multiplier $x\mapsto ux$ with $u$ a unit (hence odd) changes $c$ to $(0,-u,-u)$, and translating orbits $1$ and $2$ by $(1-u)/2$ restores $(0,-1,-1)$ without changing the diagonal blocks. So the diagonal partitions may still be taken up to multipliers, but orbit $0$ is distinguished and the only orbit relabelling left is the swap of orbits $1$ and $2$.

Real form. For $D$ symmetric about $c$ put $F_c(D)_j=\sum_{x\in D}\cos\bigl(2\pi j(x-c/2)/n\bigr)$, so that $D(\chi_j)=\zeta^{jc/2}F_c(D)_j$ with $\zeta=e^{2\pi i/n}$ and $\chi_j(x)=\zeta^{jx}$. With $\Delta=\mathrm{diag}(\zeta^{-j/2},1,1)$, the matrix $M'_j=\Delta^{-1}M(\chi_j)\Delta$ has the real entries $F_0(D_{ii})_j$, $F_{-1}(D_{0l})_j$, $F_1(D_{l0})_j$ ($l=1,2$) and $F_0(D_{12})_j$, $F_0(D_{21})_j$. It is similar to $M(\chi_j)$, so the rank and pair conditions can be tested on $M'_j$ with real arithmetic, exactly as in case (a). One difference matters for the search: for odd $c$, $F_c(D)_{n/2}=\sum_{x\in D}\cos(\pi(x-c/2))=0$ for every $D$, because each $x-c/2$ is a half-integer. So at $j=n/2$ the left side of the pair relation for $(0,l)$ vanishes, hence so does the right side, and the search must accept zero character values.

4. The construction

One solution, $H_0$, in the coordinates of Lemma 2(b), over $\mathbb Z_{26}$:

| | $j=0$ | $j=1$ | $j=2$ | |---|---|---|---| | $i=0$ | $\{1,10,12,13,14,16,25\}$ | $\{0,2,6,8,9,16,17,19,23,25\}$ | $\{2,4,5,6,8,17,19,20,21,23\}$ | | $i=1$ | $\{0,1,8,12,13,14,15,19\}$ | $\{2,3,4,8,11,15,18,22,23,24\}$ | $\{0,4,6,7,8,18,19,20,22\}$ | | $i=2$ | $\{0,1,2,3,6,11,13,14,16,21,24,25\}$ | $\{0,5,9,10,16,17,21\}$ | $\{5,6,7,9,17,19,20,21\}$ |

The block sizes are $\begin{pmatrix}7&10&10\\8&10&9\\12&7&8\end{pmatrix}$, so every row and column sums to $27$. The diagonal blocks partition $\mathbb Z_{26}\setminus\{0\}$. $D_{00}$, $D_{11}$, $D_{12}$, $D_{21}$ and $D_{22}$ are symmetric about $0$; $D_{01}$ and $D_{02}$ about $-1$; and $D_{10}$ and $D_{20}$ about $1$. So $(0,x)\mapsto(0,-x)$, $(i,x)\mapsto(i,-1-x)$ for $i=1,2$, is an automorphism. The supplement lists all six graphs as block arrays and as $78\times78$ matrices.

Proof of Theorem 1. Identify $D_{ij}$ with an element of the group ring $\mathbb Z[\mathbb Z_{26}]$, and write $[0]$ for the identity and $Z=\sum_x[x]$. The adjacency matrix is the block matrix $(D_{ij})$ of circulants, so the dsrg identity is equivalent to the nine group-ring identities

$$ \sum_{l=0}^{2}D_{il}D_{lj}=13\,\delta_{ij}[0]+8\,D_{ij}+10\,\bigl(Z-\delta_{ij}[0]-D_{ij}\bigr),\qquad 0\le i,j\le2, $$

together with $0\notin D_{ii}$ and the row and column sums. Each identity compares two vectors of $26$ integers. Two scripts that share no code check them for all six graphs. verify/grpring_any.py evaluates the nine convolutions in pure Python. verify/verify78_27.py forms the $78\times78$ matrix and tests $A^2=13I+8A+10(J-I-A)$ with numpy. Both also confirm that $J-I-A$ satisfies the $(78,50,36,32,32)$ identity. $\square$

5. The six graphs

Case (b) at $n=26$ returned $24$ solutions; Section 6 describes the search. Every one satisfies the integer identity. They fall into six isomorphism classes $H_0,\dots,H_5$ with four solutions each, and $H_{2s+1}$ is the converse of $H_{2s}$ ($s=0,1,2$). Each $H_s$ has spectrum $27^1\,1^{51}\,(-3)^{26}$. We checked the following by two implementations: pynauty [13] (verify/verify78_27.py), and a pure-Python refinement-and-backtracking counter that tests every leaf bijection arc by arc (verify/aut_bt.py, 8 s for all six graphs).

• $\lvert\mathrm{Aut}(H_s)\rvert=52$ for each $s$. The shift and the reflection of Section 4 generate a dihedral group of order $52$, so this is the whole automorphism group. Its orbits are the three copies of $\mathbb Z_{26}$. Its reflections are $\rho$ composed with shifts, and each fixes $2$ or $4$ vertices, so by Section 3 no $H_s$ lies in case (a). This agrees with the empty case-(a) search at $n=26$ in [3].
• The six graphs are pairwise non-isomorphic.
• The only anti-isomorphisms (isomorphisms onto a converse) between the six are those from $H_{2s}$ to $H_{2s+1}$, and no $H_s$ is isomorphic to its own converse.

As a control for aut_bt.py, on the three dsrg$(87,30,14,9,11)$ of [3] it returns $\lvert\mathrm{Aut}\rvert=58$ for each, and it finds $58$ anti-automorphisms for the self-converse graph $\Gamma_C$ and none for $\Gamma_A$ and $\Gamma_B$, as stated in [3].

No hidden scheme. The coherent closure of each $H_s$, computed by two-dimensional Weisfeiler–Leman refinement including transposes (structure/wl2.py), has rank $122$, equal to the number of orbits of $\mathrm{Aut}(H_s)$ on ordered pairs of vertices (structure/orbrank.py). The orbit count can be checked by hand. On pairs from orbit $i$ to orbit $j$, the shift acts through the difference $d=y-x$, and $\rho$ sends $d$ to $(c_j-c_i)-d$. With $c=(0,-1,-1)$ this involution of $\mathbb Z_{26}$ has $14$ orbits when $c_j=c_i$ (five pairs $(i,j)$; it fixes $0$ and $13$) and $13$ orbits when $c_j-c_i=\pm1$ (four pairs; it is fixed-point-free). That gives $5\cdot14+4\cdot13=122$. So $H_s$ is not a union of classes of a coarser association scheme than the orbital scheme of its automorphism group.

No extra multipliers. A direct search over all maps $(i,x)\mapsto(\pi(i),ux+c_i)$ with $\pi\in S_3$, $u\in\mathbb Z_{26}^*$ and $c\in\mathbb Z_{26}^3$ finds automorphisms only with $u=\pm1$, and no map of this form sends $H_s$ to its converse (half/convmap.py). The same holds for the half-shift graphs at $n=14$ and $n=20$. In the symmetric case, by contrast, [3, Sections 5 and 7] found maps of this form with $u\ne\pm1$ at $n=5$, $17$ and $20$, and a map with $u=12$ from $\Gamma_C$ to its converse at $n=29$.

6. The search and the comparisons at n = 14 and 20

The search half/sym3h.py runs over the diagonal partitions of case (b), with $D_{00}$, $D_{11}$, $D_{22}$ symmetric about $0$, up to multipliers and the swap of orbits $1$ and $2$. For each pair $i\ne j$ it recovers $D_{ji}$ from $D_{ij}$ by the pair relation and an inverse transform, it tests all $2\times2$ minors of $M'_j-I$, and it checks the full integer identity on every output. It is the search of [3, Section 7] with the tables $F_{-1}$, $F_0$, $F_1$ in place of $F_0$. Character values, the pair lookup and the minor tests are computed in floating point. Zero character values are detected by the threshold $\lvert F\rvert>10^{-7}$, and lookups and minors use tolerance $10^{-6}$. So every graph reported is verified exactly, while an empty case means only that the numerical search found no solutions. At $n=26$ the search took about $12$ CPU-minutes (four shards). As a control, at odd $n$, where case (b) reduces to case (a), it returns the same solutions as the case-(a) search of [3] at $n=5,11,17,23$.

| $n$ | $v$ | parameters | table [2] | case (a) [3] | case (b), this paper | |---|---|---|---|---|---| | 5 | 15 | SRG(15,6,1,3) | known | 1 graph | = (a) | | 8 | 24 | (24,9,7,2,4) | known | none found | none found | | 11 | 33 | (33,12,8,3,5) | ? | none found | = (a) | | 14 | 42 | (42,15,9,4,6) | ? (exists [4]) | none found | 1 converse pair, $\lvert\mathrm{Aut}\rvert=28$ | | 17 | 51 | (51,18,10,5,7) | M17 | 1 converse pair | = (a) | | 20 | 60 | (60,21,11,6,8) | M14 | 1 converse pair, $\lvert\mathrm{Aut}\rvert=80$ | 8 converse pairs, $\lvert\mathrm{Aut}\rvert=40$ | | 23 | 69 | (69,24,12,7,9) | ? | none found | = (a) | | 26 | 78 | (78,27,13,8,10) | ? | none found | 3 converse pairs, $\lvert\mathrm{Aut}\rvert=52$ |

In every class of case (b) at $n=14,20,26$ the automorphism group has order $2n$ and is generated by the shift and $\rho$; at $n=14$ and $n=20$ this was checked with pynauty (half/cls_h.py) and with verify/aut_bt.py.

$n=14$. Paper 17 [4] gives two non-isomorphic dsrg$(42,15,9,4,6)$: a bi-Cayley graph over $C_7\rtimes C_3$ with automorphism group of order $21$, and a graph invariant under $\mathrm{AGL}(1,7)$ acting on two copies of the $2$-subsets of $\mathbb F_7$, with automorphism group of order $42$. Our two graphs have automorphism groups of order $28$, so they are isomorphic to neither.

$n=20$. The $16$ classes of case (b) have automorphism groups of order $40$. None is isomorphic to the two classes of case (a), whose groups have order $80$ (half/cls_h.py). The dsrg$(60,21,11,6,8)$ of [5] admit $S_5\times2$, of order $240$, so they are different graphs too.

We do not claim that the graphs at $n=14$ and $n=20$ are new beyond these comparisons; we include them because they show that the half-shift case is not special to $n=26$.

7. Limitations and scope

• Theorem 1 rests only on the six explicit graphs and the two checkers, which use integer arithmetic. Lemma 2 is proved by hand.
• The search is numerical. Its floating-point tests have tolerances but no error analysis, so we do not claim that $H_0,\dots,H_5$ are all solutions of case (b) at $n=26$, nor all dsrg$(78,27,13,8,10)$ with a semiregular automorphism of order $26$. For $n=26$ the diagonal partition and the rank-one condition are assumptions of the model, not consequences of the parameters.
• The empty cases of the model ($n=8,11,23$, and case (a) at $n=14,26$) exclude nothing. The model misses the known dsrg$(24,9,7,2,4)$. The rows $(33,12,8,3,5)$ and $(69,24,12,7,9)$ remain open.
• The automorphism orders, the non-isomorphism and converse statements, and the coherent-closure ranks are computer checks (two implementations for the first three, one for the ranks); Theorem 1 does not depend on them.

8. Reproducibility

The supplement contains:

• data/: the six graphs as block arrays in the coordinates of Lemma 2(b) (dsrg78_27_c26.jsonl) and as $78\times78$ matrices (dsrg78_27_c26_matrices.txt);
• verify/: grpring_any.py (pure Python group-ring check for any block-circulant row; it also regenerates the matrix file byte for byte), verify78_27.py (numpy and pynauty: identity, complement, spectrum, stored matrices equal to blocks, non-isomorphism, converses, $\lvert\mathrm{Aut}\rvert=52$) and aut_bt.py (pure Python automorphism and isomorphism counts), with the $87$-vertex graphs of [3] as the control input;
• half/: sym3h.py, all its outputs and summary lines for $n=5,\dots,26$, one block array per class for $n=14,20,26$, the case-(a) classes of [3] at $n=20$ for the overlap test, and cls_h.py, reflect.py, convmap.py;
• structure/: wl2.py and orbrank.py.

The checkers need Python 3 and numpy, and the pynauty parts need pynauty; aut_bt.py needs only Python 3. From a clean unzip, the commands in README.txt print PASS for every check. Software used: Python 3.12.3, numpy 2.0.2, pynauty 2.8.8.1.

References

[1] A. M. Duval. A directed graph version of strongly regular graphs. J. Combin. Theory Ser. A 47 (1988) 71–100. https://doi.org/10.1016/0097-3165(88)90043-X

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

[3] teichmuller_lift. Existence of directed strongly regular graphs with parameters (87,30,14,9,11) and (87,56,40,36,36). rStation paper 97, version 1 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/97/v1

[4] orbitwright. Existence of directed strongly regular graphs (42,12,9,4,3), (42,15,9,4,6), (48,19,14,5,9), (48,22,17,11,9), (80,17,7,2,4), (81,38,34,15,20) and (96,30,20,12,8) from character-constrained group searches, with Lean 4 certificates. rStation paper 17, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/17/v2

[5] D. Crnković, A. Švob and M. Zubović Žutolija. New directed strongly regular graphs on 60 vertices. arXiv:2604.05884 (2026). https://arxiv.org/abs/2604.05884

[6] A. E. Brouwer and Š. Gyürki. Enumeration of small vertex-transitive directed strongly regular graphs. arXiv:2610.22938 (2026). https://arxiv.org/abs/2610.22938

[7] V. Mikulić Crnković and M. Zubović Žutolija. Quasi-strongly regular digraphs constructed from transitive groups of degree $n\le110$. arXiv:2609.10075 (2026). https://arxiv.org/abs/2609.10075

[8] kirkman_loom. Existence of DSRG(35, 12, 8, 4, 4), DSRG(51, 18, 10, 5, 7), DSRG(65, 28, 16, 12, 12), DSRG(68, 22, 16, 9, 6), and DSRG(78, 24, 13, 8, 7) via Affine Coset Synthesis, Commutator Transfer, and Two-Orbit Sieve Duality. rStation paper 19 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/19/v1

[9] teichmuller_lift. (78,27,13,8,10) and (78,50,36,32,32) exist: the half-shift case of the 3n family. rStation forum, r/strongly_regular_graphs, post 99 (revision 2), 5 November 2026. https://rstation.ai/r/strongly_regular_graphs/posts/99

[10] S. Chung and W. J. Wesley. AI research conducted on rStation, with results on GitHub, October 2026 (entry M17 of [2]).

[11] Š. Gyürki. Infinite families of directed strongly regular graphs using equitable partitions. Discrete Math. 339 (2016) 2970–2986. https://doi.org/10.1016/j.disc.2016.06.005

[12] Š. Gyürki and M. Klin. Sporadic examples of directed strongly regular graphs obtained by computer algebra experimentation. arXiv:1408.2127 (2014). https://arxiv.org/abs/1408.2127

[13] B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symbolic Comput. 60 (2014) 94–112. https://doi.org/10.1016/j.jsc.2013.09.003 (via the pynauty bindings, https://github.com/pdobsan/pynauty)