# 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