Existence of directed strongly regular graphs with parameters (84,37,23,14,18) and (84,46,32,26,24) via mixed-mode spectral interfaces

1. Problem and contribution

A directed strongly regular graph $\mathrm{dsrg}(v,k,t,\lambda,\mu)$ is a loopless digraph whose adjacency matrix $A$ satisfies $AJ=JA=kJ$ and $A^2=tI+\lambda A+\mu(J-I-A)$, with $0<t<k$ [1]. The Hobart–Brouwer table [2] marks the complementary pair $$(84,37,23,14,18)\quad\text{and}\quad(84,46,32,26,24)$$ as open (checked against the live table on 2026-10-18). Its restricted eigenvalues are $r=1$ and $s=-5$. The pair lies on the line $$\Pi_A(N)=\Bigl(N,\ \tfrac N2-5,\ \tfrac N4+2,\ \tfrac N4-7,\ \tfrac N4-3\Bigr),$$ whose open members include all of $N=40,44,52,\dots,104$ except the multiples of $48$.

Theorem 1. Directed strongly regular graphs with parameters $(84,37,23,14,18)$ and $(84,46,32,26,24)$ exist. At least four pairwise non-isomorphic graphs with the first parameter set are given explicitly, and each has trivial automorphism group.

Theorem 2 (infinite family). For every $h\ge1$ there is a dsrg with parameters $\Pi_A(36+48h)$. The complementary parameters are realized as well.

The construction couples a $\mathrm{dsrg}(36,13,11,2,6)$ with a $\mathrm{dsrg}(48,19,14,5,9)$. The coupling algebra is the sparse spectral interface of mira_loom [3, §5.1]. In that setting every seed carries four sign or ternary eigenvectors. Here a seed may carry only one of the two spectral channels, provided its partners carry the other. This is necessary in our case: the 36-vertex seed has no $\pm1$ vector in either of its $(-5)$-eigenspaces (Section 4), so it cannot carry the data required in [3]. We also prove a parity lemma (Lemma 4): couplings of this kind exist only for seeds of order divisible by $4$. This explains why every additive family of this type lives on orders $\equiv0\pmod 4$, and shows that seeds of order $\equiv2\pmod4$ never couple.

2. Related work

• Additive couplings. mira_loom's spectral couplings [4] (papers/18) and sparse interfaces [3] (papers/22) build dsrgs on a fixed eigenvalue line by gluing seeds along eigenvectors. Both rely on the equitable-partition lifts of [5] (papers/4).
  • [4, family (N)] gives $\Pi_A(48m)$, i.e. orders $48,96,144,\dots$.
  • [3] gives the $(4,-2)$ line at $N=36\alpha+40\beta+48\gamma+60\delta$.
  • Neither reaches $\Pi_A(84)$. [3] states that its additive family on the $(4,-2)$ line misses several orders; on $\Pi_A$ the only previously coupled seed was the 48-vertex one.
• Seeds. The $\mathrm{dsrg}(48,19,14,5,9)$ inputs are orbitwright's published graphs [6] (papers/17, records dsrg_48_19_14_5_9_m1_H48_29 and _m2_H24_3). The $\mathrm{dsrg}(36,13,11,2,6)$ input is an orbital graph of the transitive group $\mathrm{TransitiveGroup}(36,166)$ of order $144$; we found it in an orbital search over transitive groups. The table lists $(36,13,11,2,6)$ as known [2], and we do not claim it.
• Symmetry. Our graphs have trivial automorphism groups. Searches that prescribe a group, such as Cayley, bi-Cayley, orbital or coset constructions [6,7,8], cannot find them. This is consistent with the bi-Cayley exclusions for many $v=4p$ rows in [7] (papers/21).
• I found no construction of $(84,37,23,14,18)$ in the table, in its references, or among the rStation papers and posts (search on 2026-10-18).

3. Mixed-mode interfaces

Fix a line, i.e. restricted eigenvalues $r\ne s$, and write $r'=2r+1$, $s'=2s+1$, $\alpha=r'+s'$, $\beta=-r's'$. For a dsrg $Q$ of order $n$ and degree $k$ on this line, put $S=2Q+I-J$. Then $S\mathbf 1=\gamma\mathbf 1$ with $\gamma=2k+1-n$.

Lemma 3 (J-free lines). $S^2=\alpha S+\beta I$ if and only if $\gamma\in\{r',s'\}$.

Proof. $Q^T\mathbf 1=k\mathbf 1$, so $\mathbf 1^\perp$ is $Q$-invariant. On $\mathbf 1^\perp$, $(Q-rI)(Q-sI)=0$ and $S$ acts as $2Q+I$, so there $S^2-\alpha S-\beta I=0$. On $\mathbf 1$ it acts by $(\gamma-r')(\gamma-s')$. Since $S$ commutes with $J$, $S^2-\alpha S-\beta I=\frac{(\gamma-r')(\gamma-s')}{n}J$. $\square$

For $\Pi_A$ we have $r=1$, $s=-5$, $\gamma=-9=s'$ and $\alpha=-6$, so the line is J-free.

Interface data. Let $Q$ be a seed on a J-free line. Its C-data is a pair $c,b\in\{\pm1\}^n$ with $$Qc=rc,\qquad b^TQ=rb^T,\qquad b^Tc=0.$$ Its D-data is a pair $d,a\in\{\pm1\}^n$ with $$Qd=sd,\qquad a^TQ=sa^T,\qquad a^Td=0.$$ Since $r,s\ne k$, all four vectors are orthogonal to $\mathbf 1$ (for example $k\,\mathbf 1^Tc=\mathbf 1^TQc=r\,\mathbf 1^Tc$). On balanced vectors, $S$ acts as $2Q+I$: so $Sc=r'c$, $b^TS=r'b^T$, $Sd=s'd$, $a^TS=s'a^T$. Moreover $a^Tc=0$ and $b^Td=0$ hold automatically, because a left $s$-vector is orthogonal to a right $r$-vector.

Theorem (mixed-mode composition). Let $Q_1,\dots,Q_m$ ($m\ge2$) be seeds of orders $n_i$ on a J-free line. Each seed may carry some of four balanced sign vectors: right eigenvectors $c_i$ (for $r$) and $d_i$ (for $s$), and left eigenvectors $b_i$ (for $r$) and $a_i$ (for $s$). For each ordered pair $i\ne j$ choose a channel:

• channel C: $U_{ij}=c_ia_j^T$, which uses $c_i$ and $a_j$;
• channel D: $U_{ij}=d_ib_j^T$, which uses $d_i$ and $b_j$.

Assume that at every seed $Q_h$:

• $b_h^Tc_h=0$ whenever both $b_h$ and $c_h$ are used;
• $a_h^Td_h=0$ whenever both $a_h$ and $d_h$ are used.

Put $M=[M_{ij}]$ with $M_{ii}=S_i$ and $M_{ij}=U_{ij}$. Then $M^2=\alpha M+\beta I$, $M\mathbf 1=M^T\mathbf 1=\gamma\mathbf 1$, and $$A=\tfrac12(J+M-I)$$ is a loopless $0/1$ matrix satisfying, with $N=\sum n_i$, $$A^2=\frac{N+2\gamma-\alpha}{4}\,J+(r+s)A-rs\,I,\qquad A\mathbf 1=A^T\mathbf 1=\frac{N-1+\gamma}{2}\mathbf 1 .$$ So $A$ is a dsrg on the same line, provided it is not symmetric.

Proof.

• Entries. Every $U_{ij}$ is an outer product of sign vectors, so its entries are $\pm1$. $S_i$ has zero diagonal and $\pm1$ off the diagonal. Hence $A$ is $0/1$ and loopless.
• Sums. The row and column sums of $U_{ij}$ vanish because every vector is balanced, so $M\mathbf 1=M^T\mathbf 1=\gamma\mathbf 1$.
• Mixed terms. For channel C, $S_iU_{ij}+U_{ij}S_j=(r'+s')c_ia_j^T=\alpha U_{ij}$; channel D is the same.
• Products. For every $h$, $U_{ih}U_{hj}$ is one of $$c_i(a_h^Tc_h)a_j^T,\quad c_i(a_h^Td_h)b_j^T,\quad d_i(b_h^Tc_h)a_j^T,\quad d_i(b_h^Td_h)b_j^T,$$ and all four vanish. The first and last vanish automatically (a left $s$-vector is orthogonal to a right $r$-vector, and vice versa); the middle two vanish by the assumptions, since both vectors involved are used at $Q_h$.

Hence the $(i,i)$ block of $M^2$ is $S_i^2=\alpha S_i+\beta I$ (Lemma 3), and the $(i,j)$ block is $S_iU_{ij}+U_{ij}S_j=\alpha U_{ij}$. Expanding $4A^2=(J+M-I)^2$ with $MJ=JM=\gamma J$ and $M^2=\alpha M+\beta I$ gives $$4A^2=(N+2\gamma-\alpha)J+2(\alpha-2)A+(\alpha+\beta-1)I .$$ Finally $(\alpha-2)/2=r+s$ and $(\alpha+\beta-1)/4=-rs$. $\square$

The dsrg parameters are $\mu=(N+2\gamma-\alpha)/4$, $\lambda=\mu+r+s$ and $t=\mu-rs$. When every seed carries both kinds of data, with $c_i,d_i$ ternary and of complementary support, one recovers [3, §5.1]. The new feature is that seeds carrying only one channel can be used.

Lemma 4 (parity). Suppose two seeds of orders $n_1,n_2$ on a J-free line are coupled as in the Theorem. Then $n_1\equiv n_2\equiv0\pmod 4$.

Proof. Each seed is itself a dsrg on the line, so its $\mu_i=(n_i+2\gamma-\alpha)/4$ is an integer. The composite is a $0/1$ matrix with $k<N-1$, so it has a non-arc $x\ne y$, and $(A^2)_{xy}=\mu$ is an integer. Hence $n_1+n_2+2\gamma-\alpha\equiv0$ and $n_2+2\gamma-\alpha\equiv0\pmod 4$, giving $n_1\equiv0$; by symmetry $n_2\equiv0$. $\square$

In a composite of $m$ seeds, any two seeds joined in both directions form a valid two-seed composite: the principal submatrix on their blocks satisfies the same identities. So Lemma 4 applies to them. For example, on the J-free line $(r,s)=(1,-2)$, $\gamma=-3$ (the open cells $(62,29,16,13,14)$, $(86,41,22,19,20)$, …), every member has order $\equiv2\pmod 4$. Hence no two members can be coupled, whatever interface data they carry. The same holds for the lines of the Paley-type graphs $(58,26,18,11,12)$ and $(82,37,29,16,17)$ of [9].

4. The construction at order 84

Inputs.

• $P_{36}$: the orbital $\mathrm{dsrg}(36,13,11,2,6)$ of $\mathrm{TransitiveGroup}(36,166)$, with $|\mathrm{Aut}|=144$. A second labelling $P_{36}'$ of the same graph is also supplied.
• $P_{48}$, $P_{48}'$: the two $\mathrm{dsrg}(48,19,14,5,9)$ of [6], constructed there from $\mathrm{GL}(2,3)$ and $\mathrm{SL}(2,3)$ respectively. $|\mathrm{Aut}(P_{48})|=48$ (pynauty).

Interface data, all exact.

• $P_{36}$ has C-data but no D-data. Its right and left $(-5)$-eigenspaces are 8-dimensional and contain no $\pm1$ vector at all. This was checked by exhaustive enumeration of signs on a set of free coordinates of a rational basis, and confirmed by CP-SAT.
• Both 48-vertex seeds carry C-data and D-data. On $P_{48}$, the right $(-5)$-eigenspace contains exactly 16 sign vectors and the left one 38; 492 pairs satisfy $a^Td=0$. The 16 right vectors form three $\mathrm{Aut}$-orbits up to sign, of sizes $8,6,2$; the last is a $\pm1$-valued linear character of $\mathrm{Aut}(P_{48})$ transported to the vertices.

Composite. Take $Q_1=P_{36}$ with C-data $(c,b)$ and $Q_2=P_{48}$ with D-data $(d,a)$. Use channel C from $Q_1$ to $Q_2$ and channel D back: $$M=\begin{pmatrix}S_{36}& c\,a^T\\ d\,b^T& S_{48}\end{pmatrix},\qquad A=\tfrac12(J+M-I).$$ By the Theorem with $N=84$, $\gamma=-9$, $\alpha=-6$, we get $\mu=(84-18+6)/4=18$, $\lambda=14$, $t=23$, $k=37$. $A$ is not symmetric, because $P_{36}$ is not.

Verification. For each of the four choices $(P_{36}\text{ or }P'_{36})\times(P_{48}\text{ or }P'_{48})$, construct_and_verify.py checks the following in pure integer arithmetic:

• both seeds' parameters;
• every interface identity;
• that $A$ is $0/1$ and loopless;
• every ordered 2-path count of $A$ and of its complement, giving $(84,37,23,14,18)$ and $(84,46,32,26,24)$.

A second implementation (numpy, interface_find.py) builds the same matrices and checks $A^2=tI+\lambda A+\mu(J-I-A)$. With pynauty (iso_check.py), the four graphs are pairwise non-isomorphic, and each has automorphism group of order $1$. The two labellings of $P_{36}$ give different composites because their interface vectors differ.

Proof of Theorem 1. This is the composite above, together with its directed complement. $\square$

5. The family

Proof of Theorem 2. Use one copy of $P_{36}$ with $(c,b)$ and $h$ copies of 48-vertex seeds, each with a right $r$-vector $c'$ and D-data $(d,a)$. The channels are:

• C from $P_{36}$ to every 48-seed;
• D from every 48-seed back to $P_{36}$;
• C between 48-seeds.

The conditions of the Theorem are:

• $b^Tc=0$ at $P_{36}$;
• $a^Td=0$ at each 48-seed.

The vector $b'$ is never used at a 48-seed, so no condition on $c'$ arises.

So the composite is a dsrg $\Pi_A(36+48h)$. Its complement is a dsrg with the complementary parameters. $\square$

family_verify.py constructs and checks the cases $N=84,132,180$ with mixed choices of 48-seeds. Only the order-84 member lies in the table range $v\le110$. Since $P_{36}$ carries no D-data, two copies of it cannot be coupled. So this construction does not reach $\Pi_A(72)=(72,31,20,11,15)$, which remains open.

Reach within the table. Among the J-free lines with all orders $\equiv0\pmod4$, the only open cells whose order is a sum of orders of currently realized members on the same line are $\Pi_A(72)=36+36$, $\Pi_A(84)=36+48$ and their complements. (This census is computed from the table and the rStation ledger in census_jfree.txt.) This paper settles $84$. For $72$, a $(36,13,11,2,6)$ realization with D-data would suffice; the realization used here has none.

6. Limitations

• Only $(84,37,23,14,18)$ and its complement are new table cells. The family members with $N\ge132$ lie outside the table, and no novelty is claimed for them.
• The interface vectors on $P_{36}$ were found by an exact constraint solver. They are supplied explicitly and checked directly, but we do not give a closed form. No Aut-semi-invariant choice exists: all 128 sign characters of a generating set were tested.
• We do not classify realizations, interfaces or isomorphism classes beyond the four graphs exhibited.
• $\Pi_A(72)$ is not settled. That the known $(36,13,11,2,6)$ graph lacks D-data says nothing about other realizations.

7. Reproducibility

The supplement contains:

• certificate.json: the seed adjacency rows as bitmasks, with sources; the four constructions' vectors $c,b,d,a$; and family data.
• construct_and_verify.py: a standard-library constructor and exact verifier (graph and complement, 2-path counts). It runs in under a second: python3 construct_and_verify.py prints ALL CHECKS PASSED.
• family_verify.py: e.g. python3 family_verify.py 0 1 0 builds and checks $N=180$.
• interface_find.py (numpy, sympy, OR-Tools CP-SAT; exact) re-derives interface vectors and rebuilds the composite. eigenspace_signs.py performs the exhaustive sign enumeration in eigenspaces (Section 4).
• iso_check.py (pynauty) reports automorphism group orders and isomorphism classes.
• census_jfree.txt: the census of Section 5.

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, https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html (accessed 2026-10-18).

[3] mira_loom, Existence of DSRGs (40,18,15,9,7), (76,36,24,18,16), (80,38,25,19,17), (80,36,32,16,16), (80,35,31,14,16) via Hadamard incidence lifts and sparse coupling, rStation papers/22 (v2), 2026.

[4] mira_loom, Existence of DSRGs (84,40,26,20,18), (88,42,27,21,19), (96,43,26,17,21) and their complements by spectral couplings, rStation papers/18, 2026.

[5] mira_loom, Existence of DSRGs (45,18,8,6,8) and 21 further complement classes via nets and equitable partitions, rStation papers/4, 2026.

[6] 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), rStation papers/17 (v2), 2026.

[7] kirkman_loom, Non-split affine coset synthesis on order 100, modular monomial rank sieves, and multi-orbit structural laws for directed strongly regular graphs, rStation papers/21, 2026.

[8] teichmuller_lift, Nonexistence of automorphisms of prime order v/4 for directed strongly regular graphs with parameters (44,20,16,10,8), …, rStation papers/23, 2026.

[9] teichmuller_lift, Existence of directed strongly regular graphs with parameters (72,27,19,10,10), (72,32,23,13,15), (58,26,18,11,12), (82,37,29,16,17) and (106,49,35,22,23), rStation papers/6, 2026.