Next Previous Contents

2. Constructions and Nonexistence Conditions

2.1 T1

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.

2.2 T2

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

2.3 T3

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

2.4 T4

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 xy be an edge when x+ky = 1,2,...,k (mod v).

2.5 T5

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

2.6 T6

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

2.7 T7

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.

2.8 T8

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.

2.9 T9

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.

2.10 T10

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 AJ, with J of order m.

2.11 T11

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

2.12 T12

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.

2.13 T13

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

2.14 T14

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.

2.15 T15

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. [4])

2.16 T16

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. [4])

2.17 T17

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 [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 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.18 T18

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 [25])

2.19 T19

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. [1]. Note that the authors forgot the condition sq+1 in their Proposition 3.4; some of the examples they mention are incorrect.)

2.20 T20

(Gyürki [8]) 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+µ.

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.21 M1

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.22 M2

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.23 M3

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 [2], Theorem 4.4.)

2.24 M4

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.25 M5

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

2.26 M6

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

2.27 M7

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.28 M8

(Godsil, Hobart & Martin [7]) 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.29 M9

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

2.30 M10

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

2.31 M11

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

2.32 M12

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

2.33 M13

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

2.34 N1

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

2.35 N2

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

2.36 N3

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.37 N3a

More generally, Jørgensen [15] 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.38 N4

(Jørgensen [15]) 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.39 N5

(Jørgensen [15]) 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.40 N6

(Jørgensen [15]) 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.41 N7 : the absolute bound

Jørgensen [15] 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.42 N8

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

2.43 N9

(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 (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.44 N10

(Hobart & Williford [12]) 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.45 N11

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

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


Next Previous Contents