Next Previous Contents

## 2.1T1

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

## 2.2T2

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

## 2.3T3

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

## 2.4T4

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 ). Jørgensen's construction is as follows: take as vertices the integers mod v and let xy be an edge when x+ky = 1,2,...,k (mod v).

## 2.5T5

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

## 2.6T6

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

## 2.7T7

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. ) 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.

## 2.8T8

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. ) 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.

## 2.9T9

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. ) 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.

## 2.10T10

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 ) Construction: given A, consider AJ, with J of order m.

## 2.11T11

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, . (Duval ) Construction: given A, consider (A+I) ⊗ JI. In other words: apply T10 to the complements.

## 2.12T12

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. ) 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.

## 2.13T13

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 )

## 2.14T14

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 ) These parameters are a special case of those found under T12.

## 2.15T15

Let q be an odd prime power. Then there exists a dsrg with v = (q–1)(q2–1), k = q2–2, t = λ+1 = 2q–2, µ = q. (Fiedler et al. )

## 2.16T16

Let q be an odd prime power. There there exists a dsrg with v = 2q2, k = 3q–2, t = 2q–1, λ = q–1, µ = 3. (Fiedler et al. )

## 2.17T17

Let q be a prime power. There there exists a dsrg with v = hq2(q–1), k = hq(q–1), t = µ = hq–h+1, λ = (h–1)(q–1), where 0 < hq. (Olmez & Song ) 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 ) and parameters r, k, a, b, so that NJ = rJ and JN = kJ and NNtN = aN + bJ. Then the directed graph with as vertices the flags of this design and with adjacency pB → qC when the flags are distinct and p is in C is a directed strongly regular graph, and NNtN = (λ+2)N + µ(JN). These graphs have t = λ+1. Similarly, the directed graph with as vertices the antiflags of this design, with the same adjacency, is a directed strongly regular graph, and N(JN)tN = λN + µ(JN). These graphs have t = µ.

## 2.18T18

There exist dsrg with v = r(1+ab)2b, k = r(1+ab)ab, t = µ = ra2b+a, λ = ra2b+aab–1, where r, a, b are positive integers with r ≥ 2.

There also exist dsrg with v = (m+1)s, k = ls, t = µ = ld, λ = ldd, 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 )

## 2.19T19

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

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

## 2.20T20

(Gyürki ) Suppose there exists a dsrg with parameters v, k, t, λ, µ, and a partition C1, C2, ..., Ca of its vertex set into a parts of size b each, such that for each pair g, h the number of arcs from Cg to a fixed vertex x in Ch is independent of the choice of x, and is equal to µ if gh and to λ+bk if g = h. Then for any positive integer u, there exists a dsrg with parameters (ua+1)v, uv+k, ub+t, ub+λ, ub+µ. That is, with parameters u(av, v, b, b, b) + (v, k, t, λ, µ).

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 xy in Γ; there is an arc (x,g) → (y,h), where gh, 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 250u+50, 50u+7, 10u+7, 10u, 10u+1 for any positive integer u.

## 2.21T21

(Zhou, He & Chai )

## 2.22M1

If there exists a srg with parameters v, k, λ, µ, and µ = λ+1, then there is a dsrg with parameters vk, (vk–1)k, (vk–1)(kµ), (vk–2)(kµ), (vk–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).

## 2.23M2

If there exists a srg with parameters v, k, λ, µ, and µ = λ, then there is a dsrg with parameters vk, (vk)k, (vk)(kµ), (vk–1)(kµ), (vk)(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).

## 2.24M3

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 xgx and gLL. (Cf. Duval , Theorem 4.4.)

## 2.25M4

Let r be an odd prime power. Then there exists a dsrg with parameters 2r2, (r–1)(2r+1)/2, (r–1)(3r+1)/4, r(r–1)/2–1, r(r–1)/2. Construction: Take two copies of the finite field of order r2. 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 yx is a member of B, and an arrow from y' to x when yx is a member of C. Example: we get dsrg(18,7,5,3,2) and dsrg(50,22,16,10,9).

## 2.26M5

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 . (Is there also one with a simple description?)

## 2.27M6

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

## 2.28M7

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.

## 2.29M8

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

## 2.30M9

(Martinez & Araluze ) 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).

## 2.31M10

(Gyürki & Klin ) 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).

## 2.32M11

(Jørgensen ) 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.

## 2.33M12

(Martinez ) 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).

## 2.34M13

(Michel ) 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).

## 2.35N1

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

## 2.36N2

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

## 2.37N3

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 = 2v/3 = t, an excluded case.)

## 2.38N3a

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

## 2.39N4

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

## 2.40N5

(Jørgensen ) We have (kt)(µ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.)

## 2.41N6

(Jørgensen ) If λ = 0 and µ = kt, 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).)

## 2.42N7 : the absolute bound

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

(i) If s ≠ –1 then vf(f+3)/2. If moreover v(r+s2) ≠ 2(rs)(ks) then even vf(f+1)/2.

(ii) if r ≠ 0 then vg(g+3)/2. If moreover v(s+r2) ≠ 2(sr)(kr) then even vg(g+1)/2.

## 2.43N8

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

## 2.44N9

(Jørgensen ) 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 (20m,4m,m,0,m), (36m,12m,5m,2m,5m), (10m,4m,2m,m,2m), (16m,8m,5m,3m,5m), (20m,12m,9m,6m,9m), (18m,12m,10m,7m,10m).

## 2.45N10

(Hobart & Williford ) If a dsrg has an independent set of size c, then cf, and if r ≠ 0, then cg.

In particular, if λ=0 then kf, and if also r ≠ 0, then kg.

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

## 2.46N11

(Hobart & Williford ) 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 kf (resp. k-g).

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

Next Previous Contents