On combinatorial structure and algebraic characterizations of distance-regular digraphs

Let G=G(A) denote a simple strongly connected digraph with vertex set X, diameter D, and let {A_0,A:=A_1,A_2,ldots,A_D} denote the set of distance-i matrices of G. Let {R_i}_{i=0}^D denotes a partition of Xtimes X, where R_i={(x,y)in Xtimes Xmid (A_i)_{xy}=1} (0le ile D). The digraph G is distance-regular if and only if (X,{R_i}_{i=0}^D) is a commutative association scheme. In this paper, we describe the combinatorial structure of G in the sense of equitable partition and from it we derive several algebraic characterizations of such a graph.

Among else, we prove that the following (i)–(iii) are equivalent.
(i) G is a distance-regular digraph.
(ii) G is regular, has spectrally maximum diameter (D = d) and both matrices A^top and the distance-D matrix A_D are polynomial in A.
(iii) (X,{R_{ii}}_{iiinDelta}) is a commutative D-class association scheme, where Delta={(partial(x,y),partial(y,x))mid x,yin X}, and for any iiinDelta, R_{ii} denote the set of ordered pairs (x,y)in Xtimes X such that (partial(x,y),partial(y,x))=ii (here partial(x,y) denote the distance from vertex x to vertex y).

This is work in progress (it is joint work with Giusy Monzillo).

We look forward to seeing you there!