Directed Strongly Regular Graphs.

A directed strongly regular graph (DSRG) is a graph on n vertices in which every vertex has indegree and outdegree k and the number of paths of length two from a vertex x to a vertex y is t if x=y, $\lambda$ if there is an edge directed from x toy and µ otherwise. These graphs were first investigated by A. Duval (1988) and later by M. Klin et al. In J1 (see references below) we use complete computer search to find all DSRGs for some parametersets. Among these we find the first DSRG with (n,k,µ,\lambda,t)=(15,5,2,1,2). This was the last open case from Duvals list of parametersets with n<=20. In J2 a general construction of DSRGs with µ=$\lambda$ andk-1 divisible by µ is found. In a forthcoming paper (J3), several non-existence results for DSRGs are given. One of these is a generalization of the absolute bound for SRGs. Some new constructions were also found.
 

Table of feasible parameter sets for Directed Strongly Regular Graphs with  n>2k  and n<=26.

This table contains all parameter sets that satisfy the conditions in Duval's  paper.
 
 
 
n k µ \lambda  t exists ? construction / proof of non-existence no. of graphs








6 2 1 0 1 +
1
8 3 1 1 2 +
1
10 4 2 1 2 + D6.1 16
12 3 1 0 1 + D8.3 1
12 4 2 0 2 +  D7.1 + (6,2,1,0,1) 1
12 5 2 2 3 +  D7.2 + (6,2,1,0,1) 20
14 5 2 1 4 NO KMMZ,  k=t+1 0
14 6 3 2 3 + D6.1 16495
15 4 1 1 2 +  Hammersley 5
15 5 2 1 2 + J1 1292
16 6 3 1 3 NO FKM, rank 4 0
16 7 2 4 5 + D7.2 + (8,3,1,1,2) 1
16 7 3 3 4 +  FKM
18 4 1 0 3 + Duval 1
18 5 1 2 3 + FKM: Cayley graph of  S_3 x Z_3 2
18 6 3 0 3 + D7.1+(6,2,1,0,1) 1
18 7 3 2 5 + FKM
18 8 3 4 5 + D7.2+(6,2,1,0,1)
18 8 4 3 4 + D6.1
20 4 1 0 1 + D8.3 1
20 7 2 3 4 + KMMZ 8.2:  flag algebra
20 8 4 2 4 + D7.1+(10,4,2,1,2)
20 9 4 4 5 + D7.2+(10,4,2,1,2)
21 6 2 1 2 + J3: cayley graph
21 8 3 3 4 + KMMZ, flag algebra of PG(2,2)
22 9 4 3 6 ? ?

22 10 5 4 5 + D6.1
24 5 1 1 2 + J2: lambda=mu
24 6 2 0 2 + D7.1  + (12,3,1,0,1) 1
24 7 2 2 3 + D7.2  + (12,3,1,0,1)
24 8 3 2 3 + J3: Cayley graph of S_4
24 8 4 0 4 + D7.1+(6,2,1,0,1)
24 9 4 2 7 + J3: Cayley graph of S_4
24 10 4 4 8 + J3: Cayley graph of S_4
24 10 5 3 5 ? ?

24 11 3 7 8 + D7.2  + (8,3,1,1,2)
24 11 4 6 7 + D7.2  + (6,2,1,0,1)
24 11 5 5 6 + Hobart & Shaw
25 9 2 5 6 NO J3: Rank 4 0
25 10 6 1 6 NO J3: Rank 3 0
26 11 5 4 7 + J3: Aut-group Z_13
26 12 6 5 6 + KMMZ: Cayley of dihedral group









 

References:

Dx.y:

Theorem x.y in  A. M. Duval, A directed graph version of strongly regular graphs, J. Combin. Th. A 47,    71-100 (1988).
 

KMMZ:

M. Klin, A. Munemasa, M. Muzychuk and P.-H. Zieschang, Directed strongly regular graphs via coherent (cellular) algebras. Preprint Kyushu-MPS-1997-12, Kyushu University, 1997.
 

Hobart & Shaw

S. A. Hobart and T. J. Shaw, A note on a family of directed strongly regular graphs, European J. Combin. 20 (1999) 819-820.
 

FKM

F. Fiedler, M. Klin and M. Muzychuk, A census of small vertex-transitive directed strongly regular graphs, in preparation.
 
 

J1

L. K. Jørgensen, Search for directed strongly regular graphs. R-99-2016 Department of Mathematical Sciences, Aalborg University, 1999.
A pdf of this paper.
Adjacency matrices of some of the dsrg's found in paper

J2

L. K. Jørgensen, Directed strongly regular graphs with mu=lambda,   Discrete Mathematics 231  (2001) 289-293.
 
 
 

J3

L. K. Jørgensen, Non-existence of directed strongly regular graphs,
Discrete Mathematics   264 (2003) 111-126.

Results on the exact number of non isomorphic graphs are mainly from J1 and J3.

J4

Se also: Mixed Moore graphs and other dsrg