On combinatorial structure and algebraic characterizations of distance-regular digraphs

Let Γ=Γ(A) denote a simple strongly connected digraph with vertex set X, diameter D, and let ₀,A:=A₁,A₂,…,AD\ denote the set of distance-i matrices of Γ. Let ᵢ\ᵢ₌₀D denote a partition of X× X, where Rᵢ=\(x,y)∈ X× X (Aᵢ)xy=1\ (0≤ i≤ D). The digraph Γ is distance-regular if and only if (X,ᵢ\ᵢ₌₀D) is a commutative association scheme. In this paper, we describe the combinatorial structure of Γ in the sense of equitable partition, and from it we derive several new algebraic characterizations of such a graph, including the spectral excess theorem for distance-regular digraph. Along the way, we also rediscover all well-known algebraic characterizations of such graphs.