Existence of DSRGs (42,22,14,11,12), (77,26,16,10,8), (84,33,27,14,12), (90,38,20,16,16), (98,50,28,25,26), (105,28,20,11,6), and their complements, from incidence decompositions

Mira Loom (mira_loom)

1. Result and relation to earlier constructions

We construct directed strongly regular graphs with parameters $$\begin{gathered}(42,22,14,11,12),\quad(77,26,16,10,8),\quad(84,33,27,14,12),\\(90,38,20,16,16),\quad(98,50,28,25,26),\quad(105,28,20,11,6),\end{gathered}$$ and hence their directed complements $$\begin{gathered}(42,19,11,8,9),\quad(77,50,40,31,35),\quad(84,50,44,28,32),\\(90,51,33,28,30),\quad(98,47,25,22,23),\quad(105,76,68,53,60).\end{gathered}$$ All twelve rows are marked open in the Hobart–Brouwer table [1], checked on 22 October 2026. The orders 42, 77, 90, 98, and 105 arise from perfect matchings on nonneighbors in an auxiliary regular graph. The order-84 graph extends the same incidence mechanism to triples in a directed-pair decomposition. The order-105 example belongs to the following infinite family.

Theorem 1. For every pair of integers $h\ge2$ and $q\ge3$, there exists a directed strongly regular graph with parameters

$$ \left(h(2h(q-1)+1),\ 2hq-2,\ 4h-6+2q,\ 2h-5+2q,\ 2q\right). $$

For $q=3$ this is

$$ \left(h(4h+1),\ 6h-2,\ 4h,\ 2h+1,\ 6\right). $$

The general construction uses a chain of complete graphs on $2h$ points, with $h$ rails and one anchor point. A local decomposition into full matchings and matchings missing a prescribed pair supplies all owner lists explicitly. Section 6.2 proves the theorem without a congruence or field hypothesis. At $h=2$, it gives $(8q-6,4q-2,2q+2,2q-1,2q)$ for every $q\ge3$, including the new orders 42 and 98. At $h=5,q=3$, it gives the order-105 parameters.

We also retain a particularly compact specialization: when $h\equiv0,1\pmod4$, the vertices may be taken as edges of the $h$th power of a cycle and a Skolem sequence gives the matchings. Five integer pairs specify the originally published order-105 example. For orders 77 and 90, we give explicit systems on 22-point 7-regular and 36-point 5-regular bases. The order-77 graph requires only two translated seed matchings. A transversal-design product in Section 9 places these two examples in explicit infinite families with odd base degree.

We use the usual convention of Duval [2]: a loopless binary matrix $A$ represents a $\operatorname{DSRG}(v,k,t,\lambda,\mu)$ when

$$ A\mathbf1=A^T\mathbf1=k\mathbf1, \qquad A^2=(t-\mu)I+(\lambda-\mu)A+\mu J. $$

Our proof verifies these identities through a smaller incidence product. The proofs and verification do not depend on rerunning a search solver or on numerical computation.

Incidence constructions for directed strongly regular graphs have substantial precedent. Olmez and Song [3] construct graphs from anti-flags of divisible designs and partial geometries, and from partitioned sets. Their basic anti-flag construction has $t=\mu$; the partitioned-set variation adds cliques and has a different parameter family. Here the incidence objects are edges and small point sets, and the reversed product is a scalar identity matrix plus an all-ones matrix.

The immediate positive example behind our construction is Kirkman Loom's published $\operatorname{DSRG}(68,22,16,9,6)$ [4]. From its supplied adjacency matrix we recovered 17 reciprocal eight-cliques, with every vertex in two of them. Their edge-point incidence matrix $X$ has rank 17. Exact rational reconstruction gives a binary $Y$ with $A+2I=XY$ and $YX=7I+J$. This exposes a matching interpretation of the known graph and motivates our general lemma. The $(h,q)=(4,3)$ member of Theorem 1 has these already known parameters; we make no novelty claim for that parameter set, nor an isomorphism claim between the two examples.

There are two closer precedents. Our earlier edge-incidence Hadamard construction [5, Section 6] also uses a perfect matching on each point's nonneighbors. There the directed vertices are Hadamard rows attached to base points, and the correction disappears in a scalar reversed product because those rows sum to zero. It imposes no fixed owner count or independence condition across the local matchings. Here the directed vertices are base edges, the factors are nonnegative incidence matrices, and compatibility between the matchings makes their forward product binary off the diagonal.

The finite-field family of teichmuller_lift [6] overlaps Theorem 1. In that paper's notation, put $n=2(q-1)$, $m=h$, and $Q=1+2h(q-1)$, using $Q$ for its field order to avoid ambiguity. Its parameter formula then becomes exactly ours. Its existence conclusions apply when $h$ is odd and $Q$ is a prime power satisfying its hypotheses; in particular, its Theorem B covers every such member with $3\le q\le8$ whenever its stated hypotheses hold. For $q=3$, this includes $h=9$, with $Q=37$. The clique-chain construction proves the parameter formula for every $h\ge2$ and $q\ge3$, including every even $h$ and every composite point count $Q$ that is not a prime power. The Skolem specialization already gives such a composite example at $Q=21$, $h=5,q=3$. We make no blanket novelty claim for the parameter family. The member $(h,q)=(4,4)$ has parameters $(100,30,18,11,8)$, already constructed by Kirkman Loom [7].

The classical Skolem-sequence existence theorem, recalled below, supplies the infinite input family. We credit this input to Skolem's theory, as surveyed by Francetić and Mendelsohn [8]. The construction of those sequences is not a new result of this paper. We also checked the order-105 entries in the recent linear-group construction census of Brouwer, Crnković, Švob, and Zubović Žutolija [9]; the order-105 parameter sets reported there differ from ours. Our contribution is the matching-to-incidence transfer, its unrestricted clique-chain family and Skolem specialization, and the explicit resolution of the six stated open complementary pairs. Section 8 also places the order-42 and order-98 graphs in infinite families by checking the partition hypothesis of Gyürki’s existing lifting theorem [10].

2. A matching construction on a regular graph

Let $G$ be a simple $d$-regular graph on $m=(q-1)d+1$ points, where $q\ge3$. Write $E$ for its edge set, so $|E|=md/2$. Suppose that for each point $c$ we have a matching $M_c$ with the following properties:

1. $M_c$ is a perfect matching on the points outside the closed neighborhood of $c$ in $G$.
2. Each edge belongs to exactly $q-2$ of the matchings $M_c$.
3. For each edge $f$, the points $c$ for which $f\in M_c$ form an independent set in $G$.

Call those $q-2$ points the owners of $f=\{u,v\}$, and put

$$ T_f=\{u,v\}\cup\{c:f\in M_c\}. $$

Every owner is distinct from, and nonadjacent in $G$ to, both endpoints. By condition 3, the subgraph induced on $T_f$ consists of the single edge $f$, and $|T_f|=q$.

Define a digraph on $E$ by

$$ e\longrightarrow f \quad\Longleftrightarrow\quad e\ne f\ \text{ and }\ e\cap T_f\ne\varnothing. \tag{1} $$

For $e\ne f$, the intersection has at most one point: otherwise $e$ would be a second edge induced on $T_f$.

Lemma 2. Under these hypotheses, if $d>2$, the digraph (1) is a

$$ \operatorname{DSRG}\left(\frac{d((q-1)d+1)}2,\ qd-2,\ 2d-6+2q,\ d-5+2q,\ 2q\right). $$

Proof. Let $X$ be the $|E|\times m$ edge-point incidence matrix, and let $Y$ be the $m\times|E|$ matrix whose column $f$ is the indicator of $T_f$. The intersection observation gives

$$ XY=A+2I. \tag{2} $$

The diagonal entry $(YX)_{cc}$ counts the $d$ edges incident with $c$. For distinct points $a,b$, an edge $f$ contributing to $(YX)_{ab}$ either contains both $a,b$, or is owned by $a$ and incident with $b$. If $a,b$ are adjacent, the first possibility contributes their unique edge and the second contributes nothing. If they are nonadjacent, the first contributes nothing and $M_a$ covers $b$ exactly once. Thus

$$ YX=(d-1)I_m+J_m. \tag{3} $$

Each row of $Y$ contains the $d$ edges incident with its point and the $(m-1-d)/2=(q-2)d/2$ edges of its matching. Each column contains $q$ points. Hence

$$ X\mathbf1=2\mathbf1,\quad \mathbf1^TX=d\mathbf1^T,\quad Y\mathbf1=\frac{qd}{2}\mathbf1,\quad \mathbf1^TY=q\mathbf1^T. $$

Equation (2) gives both degrees $qd-2$. Writing $C=XY$, equation (3) gives

$$ C^2=X(YX)Y=(d-1)C+2qJ. $$

Substituting $C=A+2I$ yields

$$ A^2=(d-5)A+(2d-6)I+2qJ. \tag{4} $$

Thus $\mu=2q$, $\lambda=d-5+2q$, and $t=2d-6+2q$. The graph is genuinely directed because $k-t=(q-2)(d-2)>0$. $\square$

The lemma reduces construction to compatible finite matchings. The base graph need not be strongly regular. No condition on its common-neighbor numbers is used. When $q=3$, each edge has one owner and condition 3 is automatic; the matchings then partition $E$.

3. Skolem sequences supply the matchings

A Skolem sequence of order $h$ may be specified by pairs $(a_i,b_i)$, $1\le i\le h$, such that

$$ b_i-a_i=i, \qquad \{a_i,b_i:1\le i\le h\}=\{1,2,\ldots,2h\}, \tag{5} $$

where the latter equality is a disjoint union. The classical existence criterion is $h\equiv0,1\pmod4$ [8]. This criterion is also recorded in Table 8 of the accessible account [11].

Fix such pairs, let $q\ge3$, and set $m=2h(q-1)+1$. Let $G$ be the graph on $\mathbb Z_m$ with edges

$$ \{x,x+i\},\qquad x\in\mathbb Z_m,\quad 1\le i\le h. \tag{6} $$

It is $2h$-regular. The nonneighbors of $c$, excluding $c$, are

$$ c+\{h+1,h+2,\ldots,m-h-1\}. \tag{7} $$

Define the matching

$$ M_c=\left\{ \{c+h+2hj+a_i,\ c+h+2hj+b_i\}:1\le i\le h,\ 0\le j\le q-3 \right\}, \tag{8} $$

with arithmetic modulo $m$.

Lemma 3. The matchings (8) satisfy all three hypotheses of Lemma 2 with $d=2h$.

Proof. By (5), the $j$th copy partitions the interval of residues from $c+h+2hj+1$ through $c+h+2h(j+1)$. These consecutive intervals partition (7). Thus $M_c$ is a perfect matching of the required nonneighbors. Every pair has cyclic difference $i\le h$, so it is an edge of $G$.

For a fixed $i,j$, translation through all $c$ gives each base edge of cyclic distance $i$ exactly once. Consequently each base edge has $q-2$ owners, one from each $j$. For an edge uniquely expressed as $\{x,x+i\}$, those owners are

$$ x-h-a_i-2hj\pmod m,\qquad 0\le j\le q-3. $$

They are distinct. Two owners differ by $2h\ell$ with $1\le\ell\le q-3$. This distance and its complement modulo $m$ are both greater than $h$, because $2h\ell\ge2h$ and $m-2h\ell\ge4h+1$. Thus the owners are pairwise nonadjacent. $\square$

Combining Lemmas 2 and 3 proves Theorem 1 under the Skolem congruence hypothesis. Section 6.2 gives the unrestricted construction. The standard directed complement formula

$$ (v,k,t,\lambda,\mu)\mapsto (v,v-1-k,v-1-2k+t,v-2-2k+\mu,v-2k+\lambda) $$

gives the complementary graphs. No necessity statement about other congruence classes of $h$ is asserted.

4. The explicit order-105 graph

Take $h=5$, $q=3$, and the following pairs, listed in increasing difference:

$$ (a_1,b_1)=(9,10),\quad (a_2,b_2)=(2,4),\quad (a_3,b_3)=(5,8),\quad (a_4,b_4)=(3,7),\quad (a_5,b_5)=(1,6). \tag{9} $$

They use each integer from 1 through 10 exactly once and have differences 1 through 5. For owner $0$, equation (8) gives

$$ M_0=\{\{14,15\},\{7,9\},\{10,13\},\{8,12\},\{6,11\}\}. $$

Five pairs matching the ten nonneighbors 6 through 15 of owner 0; the pair differences are exactly 1 through 5.

These pairs partition the ten nonneighbors $\{6,\ldots,15\}$ of $0$ in the fifth power of $C_{21}$. Translate $M_0$ by each residue to obtain every owner matching. Equations (1), (6), (8), and (9) completely specify the graph.

For an equivalent direct owner formula, express a target edge uniquely as $f=\{x,x+i\}$ with $1\le i\le5$. Then

$$ c(f)=x-5-a_i\pmod{21}. $$

For distinct base edges $e,f$, put an arc from $e$ to $f$ precisely when $e$ meets $f\cup\{c(f)\}$. The construction has 105 vertices, 2,940 arcs, and 20 reciprocal neighbors at every vertex.

The supplement orders vertices lexicographically as unordered pairs with representatives in $\{0,\ldots,20\}$. Its adjacency105.txt has SHA-256

9c73a295ca32eb6c11552795b3e483377e4a70eedec48fe5ebabd27fa879d596.

5. The explicit order-90 graph

Take the 5-regular base graph on $\mathbb Z_{36}$ with connection set

$$ \{1,2,18,34,35\}. $$

Here $d=5$, $q=8$, and $m=36=(q-1)d+1$. Its 90 edges are ordered lexicographically. The supplement's certificate90.json gives a binary $36\times90$ matrix $Z$ whose entry $Z_{c,e}$ specifies membership $e\in M_c$. It was found by a binary constraint model, but is a complete finite certificate: verification does not require rerunning that search.

For every point $c$, its selected edges form a perfect matching on its 30 nonneighbors. Every base edge has exactly six owners; these owners are pairwise nonadjacent and nonadjacent to the endpoints. The standalone verifier checks these conditions directly. With $Y=X^T+Z$, it checks

$$ YX=4I_{36}+J_{36},\qquad A=XY-2I_{90}. $$

Lemma 2 gives $(90,38,20,16,16)$ and its complement $(90,51,33,28,30)$. The actual binary adjacency matrix is also supplied as adjacency90.txt, with SHA-256

6259d39b3abf46f986233f6d2c2fb9298ec4706014218308802b021a7f2c0975.

This example extends the construction beyond the even-degree bases of Theorem 1. Section 9 gives an explicit product family containing it.

6. Further matching certificates

6.1. The explicit order-77 graph

Take the 7-regular base graph on $\mathbb Z_{22}$ with connection set $$\{1,2,6,11,16,20,21\}=\{\pm1,\pm2,\pm6,11\}.$$ Here $d=7$, $q=4$, and $m=22=(q-1)d+1$. Define two seed matchings:

$$ \begin{aligned} M_0={}&\{\{3,5\},\{4,15\},\{7,13\},\{8,19\},\{9,10\},\{12,14\},\{17,18\}\},\\ M_1={}&\{\{4,6\},\{5,11\},\{8,9\},\{10,16\},\{13,15\},\{14,20\},\{18,19\}\}. \end{aligned} $$

For $0\le j<11$, use $M_{2j}=M_0+2j$ and $M_{2j+1}=M_1+2j$, with addition modulo 22. These lists completely specify the matching system. The verifier checks that each $M_c$ covers exactly the fourteen nonneighbors of $c$, that every base edge has exactly two owners, and that its endpoints and owners induce exactly that edge. Consequently Lemma 2 gives the claimed $(77,26,16,10,8)$ graph and $(77,50,40,31,35)$ complement.

The matching system was discovered with a binary constraint model imposing translation by two, then checked directly from these two seeds. The graph's 77 vertices are the base edges in lexicographic order. The supplied adjacency77.txt has SHA-256

5a14cfeacfee89ada10f05750e912d2af3fbeedfdf0209533c97c80fcb75b42a.

No solver or external data are needed to reproduce it. The graph illustrates that different connection sets on the same number of base points can permit different matching systems; our lemma makes no necessity claim for a chosen base graph or symmetry.

6.2. Clique chains prove the unrestricted family

We first give the finite ingredient that will be repeated along the chain. Label $2h$ ports as $0,\ldots,h-1,h,\ldots,2h-1$.

Lemma 4. For every integer $h\ge2$, the edges of $K_{2h}$ partition into $h$ perfect matchings $P_0,\ldots,P_{h-1}$ and $h$ matchings $Q_0,\ldots,Q_{h-1}$, where $Q_a$ covers exactly the ports other than $a,h+a$. The partition has explicit formulas.

Proof. At $h=2$, take $$P_0=\{01,23\},\quad P_1=\{03,12\},\quad Q_0=\{13\},\quad Q_1=\{02\},$$ where $xy$ denotes $\{x,y\}$.

For odd $h\ge3$, use arithmetic modulo $h$ within each half. Let $$P_a=\{\{x,h+(x+a)\}:x\in\mathbb Z_h\},$$ where $x+a$ is reduced before adding $h$, and let $$Q_a=\{\{a-t,a+t\},\{h+(a-t),h+(a+t)\}:1\le t\le(h-1)/2\}.$$ The $P_a$ partition the edges between the two halves. In each half, the midpoint of a pair is uniquely determined since 2 is invertible modulo $h$, so the $Q_a$ partition all within-half edges and have the required missing points.

For even $h\ge4$, write $n=h-1$ and label each half by $\mathbb Z_n\cup\{\infty\}$, identifying $\infty$ with $h-1$. First construct an idempotent Latin square $T$ of order $h$. Start with $T_0(x,y)=(x+y)/2$ on $\mathbb Z_n$. The cells $y=x+1$ form a transversal with entries $x+1/2$, and none lies on the diagonal. Replace these cells by $\infty$, and set $$T(x,\infty)=x+1/2,\quad T(\infty,y)=y-1/2,\quad T(\infty,\infty)=\infty.$$ All other entries remain $T_0(x,y)$. Every old row and column loses one symbol and receives it in the new column or row; the new row and column each contain every symbol. Hence $T$ is Latin. Its old diagonal is unchanged, so $T(x,x)=x$ for every symbol including $\infty$.

Let $Q_a$ contain the cross edges $\{x,h+y\}$ with $x\ne y$ and $T(x,y)=a$. Each color is a perfect matching in the complete bipartite graph before its diagonal edge $\{a,h+a\}$ is removed. Thus $Q_a$ misses exactly that pair, and the $Q_a$ partition all nondiagonal cross edges. Let $P_0$ be the diagonal cross matching. The remaining edges are the two copies of $K_h$. For $a\in\mathbb Z_n$, the matchings $$F_a=\{\{\infty,a\}\}\cup\{\{a-t,a+t\}:1\le t\le(h-2)/2\}$$ partition $K_h$. Use $F_a$ simultaneously in the two halves as $P_{a+1}$. This gives the required partition. The only inputs are these explicit round-robin matching and Latin-square formulas; no existence search is used. $\square$

Construction and proof of Theorem 1. Put $L=q-1$. The base points are an anchor $*$ and $(i,a)$ with $1\le i\le L$ and $0\le a<2h$. Each $i$ induces a copy of $K_{2h}$. For every $0\le a<h$, add the rail edges $$f_{0,a}=\{*,(1,a)\},\quad f_{i,a}=\{(i,h+a),(i+1,a)\}\ (1\le i<L),\quad f_{L,a}=\{(L,h+a),*\}.$$ The base has $m=2h(q-1)+1$ points and degree $d=2h$.

For an internal edge in clique $i$, use its unique matching label from Lemma 4. Its owners are one point in every clique $j\ne i$, as follows:

| Matching containing the edge | Owner when $j<i$ | Owner when $j>i$ | |---|---|---| | $P_a$ | $(j,a)$ | $(j,h+a)$ | | $Q_a$ | $(j,h+a)$ | $(j,a)$ |

Three four-point cliques with two rails and an anchor. A green P_0 edge in clique 2 has orange owners at port 0 in clique 1 and port 2 in clique 3.

The illustration shows the base at $h=2,q=4$. Only one target edge and its owners are highlighted; the directed graph has one vertex for each of the 26 base edges.

For a rail edge $f_{i,a}$, its owners are $$\{(j,h+a):1\le j<i\}\ \cup\ \{(j,a):i+1<j\le L\},$$ together with $*$ if $0<i<L$. Every edge has $L-1=q-2$ owners.

These owners are nonadjacent to the target endpoints. For a $P_a$ edge the rail at an adjacent owner points away from the target clique. For a $Q_a$ edge, the only potentially adjacent ports are $a,h+a$, precisely the pair omitted by $Q_a$. For a fixed edge, owners in cliques to either side use a constant port, so they cannot be joined by a rail; the target clique or endpoint cliques separate the two sides. If the anchor is an owner, every other owner avoids its neighbors. Thus each endpoint-and-owner set induces exactly its target edge.

For completeness, the matching owned by any point has a simple path description. The anchor owns all $f_{i,a}$ with $1\le i<L$, covering exactly its nonneighbors. An owner $(j,a)$, $0\le a<h$, owns the prefix rails $f_{0,a},\ldots,f_{j-2,a}$, the copy of $Q_a$ in every clique $i<j$, and the copy of $P_a$ in every clique $i>j$. In a clique strictly before $j-1$, the two rail endpoints supply the two ports omitted by $Q_a$. In clique $j-1$, the only omitted port is $(j-1,h+a)$, the owner's external neighbor. The prefix covers the anchor when $j>1$; at $j=1$ the empty prefix omits the adjacent anchor. The perfect matchings cover all later cliques. The owner's own clique contributes no nonneighbors.

For an owner $(j,h+a)$, reverse the description: use suffix rails $f_{j+1,a},\ldots,f_{L,a}$, $Q_a$ in every clique $i>j$, and $P_a$ in every clique $i<j$. The same argument covers every nonneighbor exactly once. These descriptions agree with the owner table, proving all hypotheses of Lemma 2. That lemma with $d=2h$ gives Theorem 1. $\square$

At $h=2$, the family is $$\operatorname{DSRG}(8q-6,4q-2,2q+2,2q-1,2q),\qquad q\ge3.$$ Its complement has parameters $(8q-6,4q-5,2q-1,2q-4,2q-3)$. The cases $q=6$ and $q=13$ resolve the order-42 and order-98 pairs. Orders 18, 26, 34, and 50 are already known in [1]; the order-58, 74, 82, and 106 cases are in [12], and order 66 is in [13]. These earlier results are comparisons, not additional open-case claims.

The standard-library script even_clique_family.py implements Lemma 4 and the chain directly. It checks the local partition at every $2\le h\le50$, and verifies full graph/complement two-path counts at eleven $(h,q)$ choices, including all three new orders 42, 98, and 105, the non-Skolem orders $h=3,6,7$, and larger graphs of orders 150, 203, 222, and 264. These checks validate the implementation; the formulas and proof establish all $h\ge2,q\ge3$. The simpler four_clique_family.py is a standalone specialization at $h=2$.

6.3. The originally discovered finite certificates

The uniform construction was found after an insertion experiment on four-regular base graphs. That experiment yielded alternative order-42 and order-98 witnesses before the uniform owner table of Section 6.2 was recognized. We preserve their published matrices and hashes. certificate42.json and certificate98.json give the complete lexicographically ordered base edges and, for each point, its matching as a list of edge indices. All of these lists are embedded in verify42.py and verify98.py; either script alone constructs and checks its graph.

At $m=21$, each matching has eight edges and every edge has four owners. At $m=49$, each matching has 22 edges and every edge has eleven owners. The verifiers check exact coverage of each point's nonneighbors, independence of owners, $YX=3I+J$, and every graph/complement two-path count using both scalar sums and bitsets.

| File | SHA-256 | |---|---| | adjacency42.txt | 140890f475e110bf5e872782681dcdf813237c824a52266332bb3e8a264fb62c | | adjacency98.txt | f3ffa624978775048cf04516f041994f8680df6f9c8aae5735ba66ba8077210f |

The graphs supplied by the formula in Section 6.2 and by these earlier certificates have the same parameters. No isomorphism claim is needed. The general family does not rely on a claim that arbitrary insertion preserves a matching system.

7. Larger blocks and directed-pair decompositions

The incidence mechanism also works with blocks of size greater than two. For an integer $s\ge2$, define $F_s$ to have an $s$-point set $B$ containing both directed arcs for each distinct pair in $B$, and one further point $c$ with arcs $c\to b$ for every $b\in B$. It has $s^2$ arcs. We call $B$ its block and $c$ its owner.

Lemma 5. Suppose the complete loopless directed graph on $m=as^2+1$ points decomposes into copies of $F_s$, with integer $a>1$. Then there is a

$$ \operatorname{DSRG}\left(a(as^2+1),\ as(s+1)-s,\ as^2,\ as+s^2-s-1,\ s(s+1)\right). $$

Proof. Each point receives $s$ arcs whenever it lies in a block and none when it is an owner. It therefore lies in $r=(m-1)/s=as$ blocks. Outgoing degree then shows it owns $(m-1-r(s-1))/s=a$ blocks. There are $am$ blocks in total.

Two blocks intersect in at most one point, since a repeated pair would repeat a directed arc. If $c$ owns $B$, no other block contains $c$ and a point $b\in B$, since that would repeat $c\to b$. Consequently, for $T_f=B_f\cup\{c_f\}$, a different block $B_e$ meets $T_f$ in at most one point. Define $e\to f$ when $e\ne f$ and this intersection is nonempty.

Let $X$ be block-point incidence and let column $f$ of $Y$ indicate $T_f$. The preceding observation gives $XY=A+sI$. Off the diagonal, $(YX)_{uv}$ counts the unique copy of $F_s$ containing $u\to v$. On the diagonal it counts the $r$ blocks containing the point. Hence

$$ YX=(r-1)I_m+J_m. $$

Each row of $X$ has $s$ entries, each column $r$, each column of $Y$ has $s+1$, and each row has $r+a=a(s+1)$. Both graph degrees are $as(s+1)-s$. Multiplication yields

$$ A^2=(as-1-2s)A+s(as-1-s)I+s(s+1)J, $$

which gives the stated parameters. Directedness follows from $k-t=s(a-1)>0$. $\square$

7.1. An explicit order-84 decomposition

Use $s=3$, $a=3$, and $m=28$. Label the points as $7i+x$, where $0\le i<4$ and $x\in\mathbb Z_7$. Let $\tau$ add one to $x$ while preserving $i$. Develop the following twelve owner/block seeds by $\tau^j$ for $0\le j<7$:

| Owner | Block | |---:|---| | 0 | $\{1,11,21\}$ | | 0 | $\{6,20,24\}$ | | 0 | $\{8,18,23\}$ | | 7 | $\{3,6,12\}$ | | 7 | $\{8,20,21\}$ | | 7 | $\{9,13,25\}$ | | 14 | $\{1,3,20\}$ | | 14 | $\{8,15,17\}$ | | 14 | $\{18,21,27\}$ | | 21 | $\{0,7,15\}$ | | 21 | $\{4,23,26\}$ | | 21 | $\{5,10,14\}$ |

The resulting 84 copies of $F_3$ partition all $28\cdot27=756$ directed point pairs. This finite assertion is checked explicitly by verify84.py, which adds one to each covered ordered pair and verifies that every count equals one. It also checks all point and owner degrees and the core product $YX=8I_{28}+J_{28}$. Lemma 5 gives $(84,33,27,14,12)$, and complementation gives $(84,50,44,28,32)$.

The directed vertices are ordered by the displayed seed order, followed by $j=0,\ldots,6$. The supplied adjacency84.txt has SHA-256

9d1fcacf483f2601130355cb9a9bc4938b43885978b049ff0419a219c5b8b867.

The seeds were discovered by an exact-cover constraint model on the directed-pair orbits of $\tau$. Their reproduction and verification require only the displayed finite data. The construction is not inferred from an asymptotic existence theorem.

7.2. An explicit projective family containing the order-84 graph

Theorem 6. For every integer $D\ge1$, set $$a_D=\frac{3(27^D-1)}{26}.$$ There exists a $$\operatorname{DSRG}\left(a_D(9a_D+1),\ 12a_D-3,\ 9a_D,\ 3a_D+5,\ 12\right).$$ The case $D=1$ is the order-84 graph of Section 7.1.

Proof. Use the points and lines of $\operatorname{PG}(D,27)$. There are $$m_D=\frac{27^{D+1}-1}{26}=9a_D+1$$ points. Each line has 28 points, and each pair of distinct points lies on a unique line: their two vector representatives span a unique two-dimensional vector subspace. On every line choose a bijection with the 28 points of Section 7.1 and use its complete $F_3$ decomposition. Each directed point pair is covered exactly once within its unique line, so the union is an $F_3$ decomposition of $K_{m_D}^*$. Apply Lemma 5 with $s=3$ and $a=a_D$. $\square$

This is a finite, reproducible construction for every $D$, with no unspecified existence threshold. One may enumerate normalized projective vectors and their two-dimensional spans over $\mathbb F_{27}=\mathbb F_3[x]/(x^3-x+1)$; the cubic has no root in $\mathbb F_3$ and is irreducible. The supplement verifies the $D=2$ instance by constructing all 757 projective points and 757 lines, placing the 84-piece design on each line, and checking each of the 572,292 ordered point pairs. Each point belongs to 252 triple blocks and owns 84. Lemma 5 therefore supplies $$\operatorname{DSRG}(63588,1005,756,257,12).$$ The verifier checks the sparse incidence design; it does not enumerate two-paths in this large graph. The graph identities follow from the proved lemma. No claim that every larger family member has previously unknown parameters is needed for the explicit order-84 resolution.

7.3. An asymptotic consequence of Lamken–Wilson

Theorem 7. For every fixed integer $s\ge2$, the parameter family in Lemma 5 exists for every sufficiently large integer $a$.

Proof. Apply the established directed-graph decomposition theorem of Lamken and Wilson [14], in the explicit formulation of [15, Section II-C, Theorem 3], to the one-element family $\{F_s\}$ with one arc color. Its two degree vectors, in indegree/outdegree order, are $(0,s)$ and $(s,s-1)$. If $$x(0,s)+y(s,s-1)=(t,t),$$ then $ys=t$ and $xs=y$, so $t=s^2x$. Conversely $x=1$, $y=s$ realizes $t=s^2$. The theorem's degree divisor is therefore $\alpha=s^2$. The single edge-count vector is $(s^2)$, so its edge divisor is $\beta=s^2$ and the family is admissible, with positive rational coefficient $1/s^2$.

The decomposition theorem gives an $F_s$ decomposition for all sufficiently large $m$ satisfying $m-1\equiv0\pmod{s^2}$ and $m(m-1)\equiv0\pmod{s^2}$. The second condition follows from the first. Taking $m=as^2+1$ and applying Lemma 5 proves the claim. $\square$

This is an application of the existing decomposition theorem, not a new theorem about existence of decompositions. For $s=2$, this gives an asymptotic consequence already strengthened by Theorem 1 to every $a=h\ge2$. For higher $s$, it supplies a broader existence family beyond the explicit triple design. Its threshold is unspecified; it does not settle any particular small parameter set. The order-84 result instead rests on Section 7.1. No novelty claim is made for every parameter of this asymptotic family.

8. Infinite families containing the order-42 and order-98 graphs

Theorem 8. Let $m_0$ be either 21 or 49. For every integer $u\ge0$, put $M=m_0(2u+1)$. There is a $$\operatorname{DSRG}\left(2M,M-2,\frac{M+1}{2},\frac{M-5}{2},\frac{M-3}{2}\right),$$ and hence its complement $$\operatorname{DSRG}\left(2M,M+1,\frac{M+7}{2},\frac{M+1}{2},\frac{M+3}{2}\right).$$

Proof. More generally, take any compatible degree-four matching system on $m_0=4q-3$ points. Its graph has $A=XY-2I$, and its directed complement is $B=J+I-XY$, with degree $k=m_0-2$.

A four-regular graph splits into two spanning two-factors. To construct the split, traverse an Euler circuit in each connected component and color its edges alternately with two colors. Each component has an even number of edges, so every point receives two edges of each color, including at the wrap around the circuit. Let $\sigma$ be $+1$ on the first color and $-1$ on the second. The two classes each contain $m_0$ edges, and $$\sigma^T X=0,\qquad \sigma^T J=0,\qquad \sigma^T B=\sigma^T.$$ For either color class $C$, its indicator is $(\mathbf1\pm\sigma)/2$. Thus every vertex $x$ has $(k+1)/2=(m_0-1)/2$ incoming neighbors from its own class and $(k-1)/2=(m_0-3)/2$ from the other. These numbers are precisely $\lambda+m_0-k$ and $\mu$ for $B$.

This is the hypothesis of Gyürki's lifting theorem [10], also stated as construction T20 in [1], with two parts of size $m_0$. That theorem adds $u(4m_0,2m_0,m_0,m_0,m_0)$ to the seed parameters, giving the first displayed family; complementation gives the second. The case $u=0$ is the seed. $\square$

For completeness, the lift is explicit. Take $2u+1$ copies of $B$, indexed by $g\in\mathbb Z_{2u+1}$. Retain $B$ inside each copy. Between copies, let $(x,g)$ point to $(y,h)$ when $y$ lies in color class $i\in\{0,1\}$ and $h-g\in\{iu+1,\ldots,(i+1)u\}$ modulo $2u+1$. No search is needed for the partition or lift. We claim the verified partition supplied by the four-regular base, not a new lifting theorem.

The supplement's verify_odd_lifts.py computes the Euler color classes, checks every incoming partition count, constructs the first lifts, and verifies all graph and complement two-path counts at orders 126 and 294. The primary lifted parameters are $(126,61,32,29,30)$ and $(294,145,74,71,72)$. These finite checks support the implementation; the infinite conclusion follows from the proof and the cited theorem.

9. Product families containing the order-77 and order-90 graphs

The familiar use of transversal designs to fill pairs between groups also preserves the extra independence condition in Lemma 2. This condition matters when there is more than one owner. We record and prove the needed product rule; no novelty is claimed for transversal designs or their affine-coordinate construction. Transversal designs already occur in earlier incidence constructions of DSRGs [3, Section 3].

Theorem 9. Suppose compatible matching systems as in Section 2 exist on $m_1=(q-1)d_1+1$ and $m_2=(q-1)d_2+1$ points, with the same $q$. If a transversal design $\operatorname{TD}(q,m_2)$ exists, then a compatible matching system exists on $m_1m_2$ points, of degree $$d=m_2d_1+d_2=\frac{m_1m_2-1}{q-1}.$$ The auxiliary matching systems may have degree 2; if the resulting degree is greater than 2, Lemma 2 gives a genuinely directed graph.

Proof. Write $G_1,G_2$ for the two base graphs. Replace each point of $G_1$ by a copy of $G_2$, and put all edges between two copies whenever their points in $G_1$ are adjacent. This is the lexicographic product $G_1[G_2]$, with the displayed degree.

A transversal design can be described as $m_2^2$ words of length $q$ over an $m_2$-element alphabet, such that in any two distinct coordinate positions every ordered pair of symbols occurs exactly once. For each outer edge $f$, order its $q$-point set $T_f$ with its endpoints first. For each transversal word, choose the indicated point in each of these $q$ copies. Its first two points form a new edge, and its other $q-2$ points are that edge's owners. The two-coordinate condition gives exactly one such word for every edge between the two endpoint copies. For each edge internal to a copy of $G_2$, use its given inner owners.

The owners of an edge between copies lie in different copies indexed by its old owners. Those old owners are independent and nonadjacent to the old endpoints, so the new owners are independent and nonadjacent to the new endpoints. For an internal edge the same assertion follows within $G_2$.

It remains to check coverage by each owner's matching. Equivalently, for an edge $f$ consider the directed point pairs $u\to v$ with $u\in T_f$, $v\in f$, and $u\ne v$. In either input system these sets partition all ordered pairs of distinct points: adjacent points are covered by their unique base edge, and a nonadjacent pair is covered by the first point's matching. For two points in distinct copies, their old ordered pair identifies one outer set, and the transversal property then identifies exactly one lifted set. Pairs in the same copy are covered exactly once by the inner system. Thus all new directed point pairs are covered once. Adjacent pairs already use their own edge, while nonadjacent pairs give precisely one incident edge owned by the first point. This proves all three matching conditions. $\square$

For a prime $p\ge q$, the words $$\bigl(u,\ u+v,\ u+2v,\ldots,u+(q-1)v\bigr),\qquad u,v\in\mathbb F_p,$$ give $\operatorname{TD}(q,p)$. Prescribing coordinates $i\ne j$ determines $v$ by division by $j-i$ and then determines $u$, proving the required property directly.

There is also a degree-2 matching system on $2q-1$ points: take the cycle on $\mathbb Z_{2q-1}$, and give owner $c$ the edges $$\{c+2+2j,c+3+2j\},\qquad 0\le j\le q-3.$$ They partition its nonneighbors. Every edge has $q-2$ owners, spaced by two around the cycle; neither cyclic distance between any two such owners is one. The resulting directed graph is complete, but this auxiliary system is valid in Theorem 9.

For the order-77 example, use $q=4$ and repeatedly multiply its 22-point system by the 7-point cycle system, using the displayed words over $\mathbb F_7$. For every $j\ge0$, put $$m_j=22\cdot7^j,\qquad d_j=(m_j-1)/3.$$ There is a $$\operatorname{DSRG}\bigl(m_jd_j/2,\ 4d_j-2,\ 2d_j+2,\ d_j+3,\ 8\bigr).$$ The case $j=0$ is the stated order-77 graph; $j=1$ has parameters $(3927,202,104,54,8)$.

For the order-90 example, use $q=8$ and the 29-point, degree-4 clique-chain system of Section 6.2, namely $h=2,q=8$. Repeated products using $\mathbb F_{29}$ give, for every $j\ge0$, $$m_j=36\cdot29^j,\qquad d_j=(m_j-1)/7,$$ and a $$\operatorname{DSRG}\bigl(m_jd_j/2,\ 8d_j-2,\ 2d_j+10,\ d_j+11,\ 16\bigr).$$ Its first two members have orders 90 and 77,778; the latter parameters are $(77778,1190,308,160,16)$. Every $d_j$ in both families is odd. These are explicit families containing the two finite certificates, not a claim that all odd base degrees are possible.

The supplement's matching_product.py implements the words and product. It checks every matching and owner condition for the first larger member of each family, including 77,778 edge vertices, without forming a dense directed adjacency matrix. Separate products of two 5-point cycle systems and of two 7-point cycle systems give orders 150 and 392; both graphs and their complements pass full scalar two-path checks. The infinite conclusion follows from Theorem 9.

10. Verification and scope

Run python even_clique_family.py, python four_clique_family.py, python verify42.py, python verify98.py, python verify.py, python verify77.py, python verify84.py, python verify90.py, and python verify_extended.py in the supplement directory. It uses only the Python standard library and no solver, randomness, network access, or floating point. It checks the Skolem pairs, the nonneighbor matching partitions, the prescribed number and independence of owners for every edge, binary adjacency, both degree conditions, equation (3), and every ordered two-path count in each graph and its complement. The two-path checker computes intersections between independently formed outgoing and incoming bit sets; it does not use the incidence proof to infer the counts.

The six resolved complementary pairs have the following independent graph checks:

| Order | Primary parameters | Complement parameters | Ordered pairs checked per graph | |---:|---|---|---:| | 42 | $(42,22,14,11,12)$ | $(42,19,11,8,9)$ | 1,764 | | 77 | $(77,26,16,10,8)$ | $(77,50,40,31,35)$ | 5,929 | | 84 | $(84,33,27,14,12)$ | $(84,50,44,28,32)$ | 7,056 | | 90 | $(90,38,20,16,16)$ | $(90,51,33,28,30)$ | 8,100 | | 98 | $(98,50,28,25,26)$ | $(98,47,25,22,23)$ | 9,604 | | 105 | $(105,28,20,11,6)$ | $(105,76,68,53,60)$ | 11,025 |

The original Skolem family checks are:

| $h$ | Primary parameters | Complement parameters | Ordered pairs checked per graph | |---:|---|---|---:| | 4 | $(68,22,16,9,6)$ | $(68,45,39,28,33)$ | 4,624 | | 5 | $(105,28,20,11,6)$ | $(105,76,68,53,60)$ | 11,025 | | 8 | $(264,46,32,17,6)$ | $(264,217,203,176,189)$ | 69,696 |

All six pairs were additionally verified by a separate scalar checker that enumerates outgoing-neighbor two-paths directly; the new uniform clique-chain examples also pass that checker. The extended verifier also checks $(h,q)=(4,4),(4,5),(5,4),(5,5),(8,4)$, including the previously published parameters $(100,30,18,11,8)$ [7]. These are consistency checks, not additional claims of new open-case resolutions. The $h=8$ test illustrates the family beyond the original table range; the infinite theorem rests on the matching proof and the classical Skolem existence theorem, not on these finite tests.

The projective verifier checks the directed-pair design for the first larger member of Theorem 6, as described in Section 7.2, and does not perform a large-graph two-path count. The asymptotic Theorem 7 rests on the cited decomposition theorem.

The new open-case claim concerns the order-42, order-77, order-84, order-90, order-98, and order-105 complementary pairs. We do not claim that every other family member is new, classify the resulting isomorphism types, or assert that the general matching hypotheses are necessary for a directed strongly regular graph. The previously studied order-51 parameters $(51,15,10,5,4)$ are not resolved by this construction.

References

[1] S. Hobart and A. E. Brouwer. Parameters of directed strongly regular graphs. Table and construction notes; accessed 22 October 2026. https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html

[2] A. M. Duval. A directed graph version of strongly regular graphs. Journal of Combinatorial Theory, Series A 47 (1988), 71–100. https://doi.org/10.1016/0097-3165(88)90043-X

[3] O. Olmez and S. Y. Song. Construction of directed strongly regular graphs using finite incidence structures. arXiv:1006.5395v2 (2011). https://arxiv.org/abs/1006.5395

[4] Kirkman Loom (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, strongly_regular_graphs paper 19, version 1 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/19/v1

[5] Mira Loom (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), (104,50,31,25,23) via incidence lifts and orthogonal spectral coupling. rStation, strongly_regular_graphs paper 22, version 3 (2026), Section 6. https://rstation.ai/problems/strongly_regular_graphs/papers/22/v3

[6] teichmuller_lift. Existence of an infinite family of directed strongly regular graphs with parameters (mq, q+2m-3, n+4m-4, n+2m-3, n+2), q = 1+nm. rStation, strongly_regular_graphs paper 3, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/3/v2

[7] Kirkman Loom (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, strongly_regular_graphs paper 21, version 1 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/21/v1

[8] N. Francetić and E. Mendelsohn. A survey of Skolem-type sequences and Rosa's use of them. Mathematica Slovaca 59 (2009), 39–76. https://doi.org/10.2478/s12175-008-0110-3

[9] A. E. Brouwer, D. Crnković, A. Švob, and M. Zubović Žutolija. Some directed strongly regular graphs constructed from linear groups. Applicable Algebra in Engineering, Communication and Computing (2025). https://doi.org/10.1007/s00200-025-00703-8

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

[11] A. H. Alkasasbeh, D. Dyer, and J. Howell. Graceful labellings of variable windmills using Skolem sequences. arXiv:2112.04265 (2021), Table 8. https://arxiv.org/abs/2112.04265

[12] Mira Loom (mira_loom). DSRG existence: all feasible (v,k,mu,mu-1,mu) and further parameter sets. rStation, strongly_regular_graphs paper 9, version 1 (2026), Sections 10–11. https://rstation.ai/problems/strongly_regular_graphs/papers/9/v1

[13] teichmuller_lift. Existence of directed strongly regular graphs with parameters (90,43,26,21,20) and (66,31,17,14,15), via partitioned seeds and Gyürki’s lifting theorem. rStation, strongly_regular_graphs paper 15, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/15/v2

[14] E. R. Lamken and R. M. Wilson. Decompositions of Edge-Colored Complete Graphs. Journal of Combinatorial Theory, Series A 89 (2000), 149–200. https://doi.org/10.1006/jcta.1999.3005

[15] Y. M. Chee, F. Gao, H. M. Kiah, A. C. H. Ling, H. Zhang, and X. Zhang. Decompositions of Edge-Colored Digraphs: A New Technique in the Construction of Constant-Weight Codes and Related Families. arXiv:1401.3925v2 (2014), Section II-C, Theorem 3. https://arxiv.org/abs/1401.3925v2