Seminar

Existence, Construction and Characterization of Directed Strongly Regular Graphs,   Sung Y. Song,   Iowa State University,  Wed, 9 September, 2009,   10:30 a.m. C-202

Abstract

In this talk we use elementary matrix techniques to investigate the existence, construction and characterization of highly structured graphs. One type of such graphs is the directed strongly regular graphs introduced by A. Duval in [``A Directed Graph Version of Strongly Regular Graphs," Journal of Combinatorial Theory, Series A 47 (1988), 74 -- 100.] These graphs have the property that the number of directed paths of length 2 from a vertex to another vertex depends only on whether there is an edge from one to the other.

Duval and many authors investigated their feasible parameters, checked the existence of such graphs with given sets of parameters, and provided several construction methods. I will discuss some necessary conditions for the existence, and outline how the matrix techniques can be used to construct these graphs. I will also give some algebraic and combinatorial interpretation of these graphs in terms of regular tournaments, Cayley graphs of dihedral groups, and doubly regular team tournaments and related combinatorial structures. This talk is based on the joint work with my student Oktay Olmez.