For every *k* > 2, there exists a dsrg with
*v* = *k*(*k*+1),
*k* = *k*,
*t* = 1,
*µ* = 1,
*λ* = 0.
(Duval
[2])
This is the special case of T8(i) obtained by taking a
2-(*k*+1,2,1) design.

If *k* is even, there exists a dsrg with
*v* = *k*^{2} – 1,
*k* = *k*,
*t* = 2,
*µ* = 1,
*λ* = 1.
(Duval
[2])
This is the special case *µ* = 1 of T4.

Let *q* be a prime power congruent 1 (mod 4).
Then there exists a dsrg with
*v* = 2*q*,
*k* = *q*–1,
*t* = *µ* = *λ*+1 = *k*/2.
(Duval
[2])

Let *µ*, *k* be positive integers such that
*µ* divides *k–1*. Then there exists a dsrg with
*v* = (*k*+1)(*k*–1)/*µ*,
*t* = *µ*+1,
*λ* = *µ*
(Jørgensen
[13]).
Jørgensen's construction is as follows: take as vertices
the integers mod *v* and let *x*→*y* be
an edge when *x*+*ky* = 1,2,...,*k* (mod *v*).

Let *n* be an odd integer.
Then there exists a dsrg with
*v* = 2*n*,
*k* = *n*–1,
*t* = *µ* = *λ*+1 = *k*/2.
(Klin et al.
[18])

Let *n* be an even integer.
Then there exists a Cayley dsrg with
*v* = 2*n*,
*k* = *n*–1,
*t* = *µ*+1 = *λ*+1 = *n*/2.
(Hobart & Shaw
[11])
These parameters are a special case of those found under T4.

If there exists a generalized quadrangle GQ(*a*,*b*),
then there exists a dsrg with
*v* = (*a*+1)(*b*+1)(*ab*+1),
*k* = *ab*+*a*+*b*,
*t* = *λ*+1 = *a*+*b*,
*µ* = 1.
(Klin et al.
[19])
This graph is obtained by looking at (point,line) flags,
where (*p*,*L*)→(*q*,*M*) when
the flags are distinct and *q* is on *L*.

If there exists a
2-(*V*,*B*,*R*,*K*,*Λ*)
design, then (i) there exists a dsrg with
*v* = *VR*,
*k* = *R*(*K*–1),
*t* = *µ* = *Λ*(*K*–1),
*λ* = *Λ*(*K*–2)
and also (ii) a dsrg with
*v* = *VR*,
*k* = *RK*–1,
*t* = *λ*+1 = *Λ*(*K*–1)+*R*–1,
*µ* = *ΛK*.
(Fiedler et al.
[5])
The former is obtained by looking at (point,block) flags,
where (*p*,*B*)→(*q*,*C*) when
*p* and *q* are distinct and *q* is on *B*.
The latter is obtained by looking at (point,block) flags,
where (*p*,*B*)→(*q*,*C*)
when the flags are distinct and *q* is on *B*.

If there exists a partial geometry with parameters
pg(*K*,*R*,*T*) then there exists a dsrg with
*v* = *RK*(1 + (*K*–1)(*R*–1)/*T*),
*k* = *RK*–1,
*t* = *λ*+1 = *K*+*R*–2,
*µ* = *T*.
(Fiedler et al.
[5])
This graph is obtained by looking at (point,line) flags,
where (*p*,*L*)→(*q*,*M*) when
the flags are distinct and *q* is on *L*.
Of course T7 is the special case *T* = 1 of this.

If there exists a dsrg with parameters *v*, *k*,
*t*, *λ*, *µ*, and *t* = *µ*,
then for each positive integer *m* there also is a dsrg
with parameters *mv*, *mk*, *mt*, *m*λ*,
*m*µ*.
(Duval
[2])
Construction: given *A*, consider *A* ⊗ *J*,
with *J* of order *m*.

If there exists a dsrg with parameters *v*, *k*,
*t*, *λ*, *µ*, and *t* = *λ*+1,
then for each positive integer *m* there also is a dsrg
with parameters *mv*, *m*(*k*+1)–1,
*m*(*t*+1)–1,
*m*(*λ*+2)–2,
*mµ*.
(Duval
[2])
Construction: given *A*, consider
(*A*+*I*) ⊗ *J* – *I*.
In other words: apply T10 to the complements.

Suppose *n*, *d*, and *c* are positive integers such
that *c* < *n*–1 and *c* divides *d*(*n*–1).
Then there exists a dsrg with parameters
*v* = *dn*(*n*–1)/*c*,
*k* = *d*(*n*–1),
*t* = *µ* = *c*.*d*,
*λ*= (*c*–1)*d*.
(Godsil et al.
[7])
Construction: take the complete directed graph on *n* vertices,
each edge with multiplicity *d*. Colour the edges with
*d*(*n*–1)/*c* colours in such a way that
all in- and outdegrees for each fixed colour are *c*.
Let the vertices of the dsrg be the arrow bundles consisting
of all arrows of a given colour starting at a given vertex.
Make a directed edge from one arrow bundle to another when
one of the edges of the first one ends at the vertex of the second one.

There do exist dsrg with parameters
(*v*,*k*,*t*,*λ*,*µ*) =
(24,8,3,2,3), (24,9,7,2,4), (24,10,8,4,4), (26,11,7,4,5).
(Jørgensen
[15])

Let *m* and *q* be positive integers, and assume that
each prime power in the complete factorization of *m* is 1
mod *q*. Then there exists a Cayley dsrg with
*v* = *m*.*q*,
*k* = *m*–1,
*t* = *µ* = *λ*+1 = (*m*–1)/*q*.
(Duval & Iourinski
[3])
These parameters are a special case of those found under T12.

Let *q* be an odd prime power. Then there exists a dsrg with
*v* = (*q*–1)(*q*^{2}–1),
*k* = *q*^{2}–2,
*t* = *λ*+1 = 2*q*–2,
*µ* = *q*.
(Fiedler et al.
[4])

Let *q* be an odd prime power. There there exists a dsrg with
*v* = 2*q*^{2},
*k* = 3*q*–2,
*t* = 2*q*–1,
*λ* = *q*–1,
*µ* = 3.
(Fiedler et al.
[4])

Let *q* be a prime power. There there exists a dsrg with
*v* = *hq*^{2}(*q*–1),
*k* = *hq*(*q*–1),
*t* = *µ* = *hq–h+1*,
*λ* = (*h*–1)(*q*–1),
where 0 < *h* ≤ *q*.
(Olmez & Song
[24])
Construction: take the antiflags (p,L) in a net consisting of *h*
parallel classes of lines in AG(2,*q*), and let
pL→rM when p is on M.

More generally, consider a 1½-design with point-block incidence
matrix *N* (cf. Neumaier
[23])
and parameters *r*, *k*, *a*, *b*, so that
*NJ* = *rJ* and *JN* = *kJ*
and *NN ^{t}N* =

There exist dsrg with
*v* = *r*(1+*ab*)^{2}*b*,
*k* = *r*(1+*ab*)*ab*,
*t* = *µ* = *ra*^{2}*b*+*a*,
*λ* = *ra*^{2}*b*+*a*–*ab*–1,
where *r*, *a*, *b* are positive integers
with *r* ≥ 2.

There also exist dsrg with
*v* = (*m*+1)*s*,
*k* = *ls*,
*t* = *µ* = *ld*,
*λ* = *ld*–*d*,
where *d*, *l*, *m*, *s* are positive integers
with *dm* = *ls*, and 1 ≤ *l* < *m*.

There also exist dsrg with
*v* = (*m*+1)*s*,
*k* = *ls*+*s*–1,
*t* = *ld*+*s*–1,
*λ* = *ld*+*s*–2,
*µ* = *ld*+*d*,
where *d*, *l*, *m*, *s* are positive integers
with *dm* = *ls*, and 1 ≤ *l* < *m*.
(Olmez & Song
[25])

Let *q* be a prime power, and let *s* ≤ *q*+1.
Then there exists a dsrg with parameters
*v* = *sq*^{2},
*k* = *sq*–1,
*t* = *q*+*s*–2,
*λ* = *q*+*s*–3,
*µ* = *s*–1.

Let *q* be a prime power, and let *s* ≤ *q*.
Then there exists a dsrg with parameters
*v* = *sq*^{2},
*k* = (*s*+1)*q*–1,
*t* = 2*q*+*s*–3,
*λ* = *q*+*s*–3,
*µ* = *s*+1.
(Araluze et al.
[1].
Note that the authors forgot the condition
*s* ≤ *q*+1 in their Proposition 3.4;
some of the examples they mention are incorrect.)

(Gyürki
[8])
Suppose there exists a dsrg with parameters *v*, *k*,
*t*, *λ*, *µ*, and a partition *C*_{1},
*C*_{2}, ..., *C*_{a} of its vertex set into
*a* parts of size *b* each, such that for each pair
*g*, *h* the number of arcs from *C*_{g}
to a fixed vertex *x* in *C*_{h}
is independent of the choice of *x*, and is equal to *µ* if
*g* ≠ *h* and to *λ*+*b*–*k* if
*g* = *h*.
Then for any positive integer *u*, there exists a dsrg with parameters
(*ua*+1)*v*, *uv*+*k*, *ub*+*t*, *ub*+*λ*, *ub*+*µ*.

Construction: Let Γ be the given dsrg, with vertex set *V*.
The new graph Γ' has vertex set *V* × {0, 1, ..., *ua*}.
There is an arc (*x*,*g*) → (*y*,*g*)
if there is an arc *x* → *y* in Γ;
there is an arc (*x*,*g*) → (*y*,*h*),
where *g* ≠ *h*, when *h* is in
*g* + (*i*–1)*u* + {1,...,*u*}
(mod *ua*+1).

If Γ has eigenvalues *k*, *r*, *s*,
then the eigenvalues of Γ' are *uv*+*k*,
*r*, *s*.

For example, if Γ is the Hoffman-Singleton graph with parameters
50, 7, 7, 0, 1 and the partition is one into five Petersen graphs
(so that *a*=5, *b*=10), we find dsrg Γ'
with parameters 250*u*+50, 50*u*+7, 10*u*+7,
10*u*, 10*u*+1 for any positive integer *u*.

If there exists a srg with parameters *v*, *k*,
*λ*, *µ*, and *µ* = *λ*+1,
then there is a dsrg with parameters *vk*,
(*v*–*k*–1)*k*,
(*v*–*k*–1)(*k*–*µ*),
(*v*–*k*–2)(*k*–*µ*),
(*v*–*k*–1)(*k*–*µ*).
Construction: take the edges of the srg, and let xy→uv when
u is at distance 2 from y.
Example: the Petersen graph produces a dsrg(30,18,12,10,12).

If there exists a srg with parameters *v*, *k*,
*λ*, *µ*, and *µ* = *λ*,
then there is a dsrg with parameters *vk*,
(*v*–*k*)*k*,
(*v*–*k*)(*k*–*µ*),
(*v*–*k*–1)(*k*–*µ*),
(*v*–*k*)(*k*–*µ*).
Construction: take the edges of the srg, and let xy→uv when
u is at distance 0 or 2 from y.
Example: from srg(16,6,2,2) we get a dsrg(96,60,40,36,40).

There exists a dsrg(18,4,3,0,1).
Construction: Consider AG(2,3) with a fixed direction, say vertical.
Let the vertices of the dsrg be the 9 points and the 9 non-vertical lines.
Take an undirected edge (pair of opposite directed edges) for each
incident (point,line) pair. Let *g* be an automorphism of
order 3 moving points vertically, and add directed edges
*x*→*gx* and *gL*→*L*.
(Cf. Duval
[2], Theorem 4.4.)

Let *r* be an odd prime power. Then there exists a
dsrg with parameters
2*r*^{2},
(*r*–1)(2*r*+1)/2,
(*r*–1)(3*r*+1)/4,
*r*(*r*–1)/2–1,
*r*(*r*–1)/2.
Construction: Take two copies of the finite field of order *r*^{2}.
Join vertices in one copy when they differ by a square, in the other
when they differ by a non-square. Thus, both halves are undirected
(Paley) graphs. View the field as AG(2,*r*) and pick two
sets, *B* and *C*, each the union of (*r*–1)/2
mutually parallel lines, where *B* and *C* use different
directions.
Make an arrow from *x* in the first copy to *y*'
in the second copy when *y*–*x* is a member of *B*,
and an arrow from *y*' to *x* when *y*–*x*
is a member of *C*.
Example: we get dsrg(18,7,5,3,2) and dsrg(50,22,16,10,9).

There exist precisely 1292 nonisomorphic dsrg(15,5,2,1,2), namely 1174, 100, 10, 5, 3 with full automorphism group of order 1, 2, 3, 4, 5, respectively, according to Jørgensen [14]. (Is there also one with a simple description?)

There exist precisely 16495 nonisomorphic dsrg(14,6,3,2,3), see below. Maybe the first was given by Duval [2].

The tensor product of two ±1 matrices belonging to dsrgs in the
1-dimensional case, is again
a dsrg in the 1-dimensional case.
Here one may also take *I* of order 2.

(Godsil, Hobart & Martin
[7])
Given a dsrg with adjacency matrix *A*, such that
*µ*=*λ* and *v*=4*k*–4*µ*,
and a Hadamard matrix *H* of order *c* with constant row and
column sums *d*, and ones on the diagonal, put
*B* = *J* – 2*A* and
*B'* = *B* ⊗ *H*.
The parameter conditions say that *B* is a ±1 matrix
with 1's on the diagonal, constant row and column sums, and with
*B*^{2} a multiple of *I*. Clearly, the same holds for *B'*.
Hence *A'*, given by *B'* = *J* – 2*A'*,
is again the adjacency matrix of a dsrg. The parameters are
*v'* = *vc*,
*k'* = 2*c*(*k*–*µ*)+*d*(2*µ*–*k*),
*t'* = *c*(*k*+*t*–2*µ*)+*d*(2*µ*–*k*),
*λ'* = *µ'* = *c*(*k*–*µ*)+*d*(2*µ*–*k*).
Note that *c* = *d*^{2}.

(Martinez & Araluze
[20])
Using partial sum families in a cyclic group, the authors construct
examples for (*v*,*k*,*t*,*λ*,*µ*)
= (27,10,6,3,4), (28,7,2,1,2), (30,13,8,5,6), (32,9,6,1,3),
(32,10,7,3,3), (33,11,4,3,4), (34,14,12,5,6), (34,15,9,6,7),
(35,8,4,1,2), (39,10,6,1,3), (40,17,11,6,8), (42,14,5,4,5),
(44,10,4,3,2), (45,14,6,5,4).

(Gyürki & Klin
[9])
Using unions of classes in an association scheme, the authors construct
examples for (*v*,*k*,*t*,*λ*,*µ*)
= (30,13,11,6,5), (32,9,6,1,3), (32,13,9,4,6), (32,14,10,6,6),
(36,13,7,4,5), (36,13,11,2,6), (39,10,6,1,3), (39,12,4,3,4),
(39,14,6,5,5), (39,16,12,7,6), (45,16,8,5,6), (48,10,6,2,2),
(48,13,7,2,4), (50,16,10,3,6), (50,23,13,10,11), (54,8,3,2,1),
(54,16,12,6,4), (54,19,9,6,7), (54,20,16,6,8), (54,21,17,8,8),
(54,25,14,11,12), (60,13,5,2,3), (60,26,20,10,12), (63,22,10,7,8),
(72,19,11,2,6), (72,20,14,4,6), (72,21,15,6,6), (72,22,9,6,7),
(72,26,10,8,10), (84,29,19,6,12), (84,31,17,12,11), (84,39,27,18,18),
(90,28,16,10,8), (105,36,16,11,13).

(Jørgensen [17]) There exist dsrgs with parameters (36,10,5,2,3), (96,13,5,0,2), (108,10,3,0,1) related to mixed Moore graphs.

(Martinez [21]) Using partial sum families one can construct dsrgs with parameters (18,5,3,2,1), (18,7,5,2,3), (27,8,4,3,2), (27,10,6,3,4), (32,7,4,3,1), (32,9,6,1,3), (36,11,5,4,3), (36,13,7,4,5), (39,16,12,7,6), (45,14,6,5,4), (45,16,8,5,6), (48,11,5,4,2), (50,9,5,4,1), (64,15,6,5,3), (75,14,6,5,2).

(Michel [22]) From products of groups one gets several infinite families of parameters that cover the small examples (80,22,10,6,6), (81,28,12,9,10), (99,34,14,11,12).

There is no dsrg with *v* = 14, *k* = 5, *t* = 4,
*λ* = 1, *µ* = 2.
(Klin et al.
[18])

There is no dsrg with *v* = 32, *k* = 6, *t* = 5,
*λ* = 1, *µ* = 1.
(Jørgensen
[13])

If *t* = *µ* and *g* = 2 then *k*
divides *v*.
(Indeed, all rows of *A* are linear combinations of two
rows and the all-one vector. If *k* does not divide *v*
then the all-one vector cannot be used, unless
*k* = 2*v*/3 = *t*, an excluded case.)

More generally, Jørgensen
[15]
shows that if *g* = 2 then we have either
(*v*,*k*,*t*,*λ*,*µ*) =
(6*m*,2*m*,*m*,0,*m*) or
(*v*,*k*,*t*,*λ*,*µ*) =
(8*m*,4*m*,*3m*,*m*,*3m*).

(Jørgensen
[15])
If *g* = 3 then we have either
(*v*,*k*,*t*,*λ*,*µ*) =
(6*m*,3*m*,*2m*,*m*,*2m*) or
(*v*,*k*,*t*,*λ*,*µ*) =
(12*m*,3*m*,*m*,0,*m*).

(Jørgensen
[15]) We have
(*k*–*t*)(*µ*–*k*+*t*) ≤
*λ*.*t*.
(Indeed, fix a point x and look at triangles xyz where xy
is a directed edge and xz is an undirected edge, and yz
may be directed (in the yz direction) or undirected.
There are at least the LHS and at most the RHS such triangles.)

(Jørgensen
[15])
If *λ* = 0 and *µ* = *k*–*t*,
then *v* is a multiple of 3*µ*.
(Indeed, since *λ* = 0, the *µ* triangles
on a directed edge contain directed edges only, and one sees
that the directed edges form a graph of which each connected
component has 3*µ* vertices (since it is the
*µ*-coclique extension of a directed triangle).)

Jørgensen [15] showed that dsrg's satisfy the usual absolute bound:

(i) If *s* ≠ –1 then *v* ≤ *f*(*f*+3)/2.
If moreover *v*(*r*+*s*^{2}) ≠
2(*r*–*s*)(*k*–*s*) then even
*v* ≤ *f*(*f*+1)/2.

(ii) if *r* ≠ 0 then *v* ≤ *g*(*g*+3)/2.
If moreover *v*(*s*+*r*^{2}) ≠
2(*s*–*r*)(*k*–*r*) then even
*v* ≤ *g*(*g*+1)/2.

There is no dsrg with *v* = 30, *k* = 7, *t* = 5,
*λ* = 0, *µ* = 2.
(Jørgensen
[15])

(Jørgensen
[16])
In the 2-dimensional case, if *A* has rank 5, so that
*t* = *µ* and *g* = 4
(i.e., *k* = 4(*µ*–*λ*)),
then the parameter set
(*v*,*k*,*t*,*λ*,*µ*)
is one of (20*m*,4*m*,*m*,0,*m*),
(36*m*,12*m*,5*m*,2*m*,5*m*),
(10*m*,4*m*,2*m*,*m*,2*m*),
(16*m*,8*m*,5*m*,3*m*,5*m*),
(20*m*,12*m*,9*m*,6*m*,9*m*),
(18*m*,12*m*,10*m*,7*m*,10*m*).

(Hobart & Williford
[12])
If a dsrg has an independent set of size *c*,
then *c* ≤ *f*, and if *r* ≠ 0, then
*c* ≤ *g*.

In particular, if *λ*=0 then *k* ≤ *f*,
and if also *r* ≠ 0, then *k* ≤ *g*.

In particular, if *λ*=1 then *k/3* ≤ *f*,
and if also *r* ≠ 0, then *k/3* ≤ *g*.

(Hobart & Williford
[12])
Consider the graph induced on the outneighbours of a fixed vertex *x*.
If *k* > *f* (or *k* > *g*)
then it has eigenvalue *s* (resp. *r*) with
geometric multiplicity at least *k*–*f*
(resp. *k*-*g*).

It follows that if *k* > *f* (or *k* > *g*) then
*λ* ≥ –*s* (resp. *λ* ≥ *r*).

Next Previous Contents