TWO RESULTS CONCERNING

DISTANCE-REGULAR DIRECTED GRAPHS

D. Combe and D.E. Taylor

School of Mathematics and Statistics University of Sydney N.S.W. 2006 Australia.

10 June 1999

Abstract. The study of distance-regular directed graphs can be reduced to that of short distance-regular directed graphs. We consider the eigenspaces of the intersection matrix of a short distance-regular directed graph and show that nearly all the eigenvalues are nonreal. Next we show that a nontrivial short distance-regular directed graph is primitive.

1. Introduction

Distance-regular and distance-transitive directed graphs are the directed version of distance-regular and distance-transitive (undirected) graphs. However, in the directed case, there are very few examples. Distance-transitive directed graphs were introduced by Lam [7] and have also been considered by others, for example in [1], [2], [3], [4], [8], [9], [10] and [11].

A directed graph or digraph Γ is a pair Γ = (V, E) consisting of a finite set V of vertices and a set E of edges. The elements of E are ordered pairs of distinct elements of V. A (directed) path of length h from x to y is a sequence of vertices x = x_{0}, x_{1}, …, x_{h} = y, such that h > 0 and (x_{i}, x_{i+1}) ∈ E for i = 0, 1 …, h − 1. If x = y then the path is a circuit. A digraph Γ is strongly connected if, for any x, y ∈ V, there is a path from x to y. The length of a shortest path from a vertex x to a vertex y is the distance from x to y, and is denoted d(x, y). The diameter d of a strongly connected digraph is the maximum value taken by this distance function over all x, y ∈ V. The girth g is the minimum length of a circuit. Clearly g ≤ d + 1.

For any vertex x we define the ith directed shell Γ_{i}(x) to be

Γ_{i}(x) = {w ∈ V : d(x, w) = i}.

A digraph Γ is distance-regular if it is strongly connected and for all vertices x and y, and for 0 ≤ i, j ≤ d, |Γ_{i}(x) ∩ Γ_{j}(y)| depends only on i, j and d(x, y).

An automorphism of a digraph is a permutation ρ of the vertices which preserves the edges, that is (x, y) ∈ E if and only if (x^{ρ}, y^{ρ}) ∈ E. A strongly connected digraph is distance-transitive if, for any vertices x, y, z, w with d(x, y) = d(z, w), there is an automorphism of the digraph such that x^{ρ} = z and y^{ρ} = w. Clearly a distance-transitive digraph is distance-regular.

A directed circuit with n vertices is an example of a distance-transitive digraph with girth g = d+1 = n. For each prime power q ≡ 3 (mod 4), the Paley tournament with q vertices is the digraph whose vertices are the elements of the finite field with q elements. There is an edge from x to y if and only if y−x is a nonzero square in the field. A Paley tournament is a distance-transitive digraph with girth g = d + 1 = 3.

Let Γ be a distance-regular digraph. A distance-regular digraph of girth 2 is essentially the same as the underlying undirected graph, so from now on we always assume Γ has girth at least 3. We define an involutory permutation on the set {0, 1, …, g}, by setting 0^{∗} = 0, g^{∗} = g and i^{∗} = g − i for 0 < i < g. Damerell [3] showed that for any vertices x, y of Γ, the distance d(y, x) = d(x, y)^{∗} and hence that the girth and diameter differ by at most 1. Damerell reduced the classification of distance-regular directed graphs to those which are short, that is those which satisfy g = d + 1. A distance-regular digraph in which g ≠ d + 1 is called long.

Leonard and Nomura [8] showed that a short distance-regular directed graph which is not simply a directed circuit has girth at most 8, and, furthermore, that there always exist edges within the first directed shell of any vertex. There are examples of short distance-regular directed graphs of girth 3 or 4, see for example [7], [4], or [9]. Bannai, Cameron and Kahn [1] showed that a short distance-transitive directed graph which has an odd girth is a Paley tournament.

In §2 we recall definitions and results concerning the adjacency and intersection algebras of a short distance-regular digraph and prove the first result of this paper. This result was known () in the case where the digraph has a distance transitive group of automorphisms.

Theorem A. Let C be the intersection matrix of a short distance-regular directed graph with girth g and valency k. Then C has g distinct eigenvalues, and

i) if g is odd, then C has exactly one real eigenvalue k, and

ii) if g is even, then C has exactly two real eigenvalues, one of which is k, and the other of which is a negative real number.

In §3 we recall the definition of primitivity for a directed graph. Damerell showed that a long distance-regular digraph is imprimitive. It follows immediately that its automorphism group acts imprimitively on the vertices. For short distance-regular digraphs we prove the following theorem:

Theorem B. Let Γ be a short distance-regular directed graph with valency k and n vertices.

i) If k = 1 then Γ is a directed circuit with n vertices and is primitive if and only if n is prime.

ii) If k > 1 then Γ is primitive.

Corollary. Let Γ be a short distance-regular directed graph with valency k > 1. Then any distance-transitive group of automorphisms acts primitively on the vertices.

2. Adjacency and intersection matrices.

In this section we will always assume that Γ is a short distance-regular digraph with n vertices, diameter d, girth g = d + 1, and labelled vertex set V = {x_{1}, x_{2}, …, x_{n}}. For i, j, k = 0, 1, … d, the intersection numbers p_{i,j,k} are

p_{i,j,k} = |Γ_{i}(x) ∩ Γ_{j^{∗}}(y)|, for x, y any vertices of Γ with d(x, y) = k.

For any matrix M of complex numbers, M^{T} denotes the transposed matrix, \overline{M} denotes the complex conjugate.

For any digraph with vertex set {y_{1}, y_{2}, …, y_{m}} the adjacency matrix A is the matrix of 0s and 1s whose (r, s)-th entry is (A)_{r,s}, where

(A)_{r,s} = 1 if and only if (y_{r}, y_{s}) is an edge.

For i = 0, 1, …, d, the distance matrix A_{i} of Γ is the matrix of 0s and 1s with

(A_{i})_{r,s} = 1 if and only if d(x_{r}, x_{s}) = i.

Thus A_{0} is the identity matrix. The matrix A = A_{1} is the adjacency matrix of the digraph. It is clear that in general A_{i^{∗}} = A_{i}^{T}, and that A_{i} is a symmetric matrix if and only if i = 0 or g/2.

By counting paths it is easy to see that, for 0 ≤ i, h ≤ d, the distance matrices satisfy A_{i}A_{h} = ∑_{j=0}^{d} p_{i,h,j}A_{j}. Hence the linear span of A_{1}, A_{2}, …, A_{d}, is closed under multiplication and is thus an algebra. This is called the adjacency algebra of the digraph. It is well known (see [7]) that the adjacency algebra is commutative with dimension g = d+1. Each of the sets {A_{0}, A_{1}, …, A_{d}} and {I, A^{1}, A^{2}, …, A^{d}} forms a basis, where the A_{i} are the distance matrices and the A^{i} are the powers of A.

Set V_{0} = 1. For each i = 0, 1, …, d − 1, the product A_{i}A = ∑_{j=0}^{i+1} p_{i,1,j}A_{j}, and p_{i,1,i+1} > 0. For i = 1, 2, … d, this equation recursively defines real polynomials V_{i}(x) of degree i such that V_{i}(A) = A_{i}.

The algebra A acts on itself by multiplication on the right. For h = 0, 1, …, d, the h-th intersection matrix C_{h} is defined to be the (d + 1) × (d + 1) matrix whose (i, j)-th entry is

(C_{h})_{i,j} = p_{i,h,j} = p_{h,i,j}.

The matrix C_{0} is the identity matrix. The matrix C = C_{1} is called the intersection matrix. Right multiplication by A_{h}, regarded as a linear mapping of the adjacency algebra to itself with respect to the basis {A_{0}, A_{1}, …, A_{d}}, can be faithfully represented by the transposed h-th intersection matrix, C_{h}^{T}.

The two matrices A and C have the same minimum polynomial and so have the same eigenvalues.

The matrix A is a real nonsymmetric matrix, which commutes with its transpose. Therefore A is a normal matrix and hence is diagonalizable and there is a basis of ℂ^{n} which consists of eigenvectors of A. Since the minimum polynomial of A has degree d+1, A has d+1 distinct eigenvalues, which we denote by λ_{0} = 1, λ_{1}, …, λ_{d}.

We call an eigenvector of a matrix standard if its first coordinate is 1.

Lemma 2.1. Let λ be an eigenvalue of C. Then

i) we can construct a unique standard left eigenvector w(λ), and a unique standard right eigenvector v(λ) corresponding to λ,

ii) for i = 0, 1, …, d, the eigenvectors w(λ) and v(λ) are standard left and right eigenvectors of C_{i} with corresponding eigenvalue V_{i}(λ),

iii) the eigenvalue λ is real if and only if v(λ) is a real vector if and only if w(λ) is a real vector, and

iv) v(\overline{λ}) = \overline{v(λ)} and w(\overline{λ}) = \overline{w(λ)}.

Proof. Let λ be any eigenvalue of C. Then corresponding right and left eigenvectors in standard form can be constructed in the following manner:

If v = [v_{0}, v_{1}, …, v_{d}]^{T} then the equation Cv = λv becomes ∑_{j=0}^{i+1} p_{i,1,j}v_{j} = λv_{i}. Setting v_{0} = 1 we get the same system of equations as for the distance matrices. Therefore the entry v_{i} = V_{i}(λ). The vector v(λ) = [1, …, V_{i}(λ), …, V_{d}(λ)]^{T} is the unique standard right eigenvector corresponding to λ.

Similarly a left eigenvector w(λ) corresponding to λ can be constructed. If w = [w_{0}, w_{1}, …, w_{d}] then the system wλ = wC becomes ∑_{i=0}^{d} w_{i}p_{1,i,j} = λw_{j}. This time each w_{j} is w_{d} times a polynomial in λ . Setting w_{d} = \frac{λ}{k} ≠ 0 , we get λw_{0} = w_{d}p_{d,1,0} = w_{d}p_{1,d,0} = \frac{λ}{k}k = λ. Therefore w_{0} = 1, and w(λ) = [1, …, \frac{λ}{k}], the unique standard left eigenvector corresponding to λ.

For each i, C_{i} = V_{i}(C), and so an eigenvector of C corresponding to eigenvalue λ, is an eigenvector of C_{i} with corresponding eigenvalue V_{i}(λ).

Finally, since C is a real matrix, v(\overline{λ}) = \overline{v(λ)} and w(\overline{λ}) = \overline{w(λ)}. Furthermore the eigenvalues corresponding to real eigenvectors must be real. Conversely, if λ is a real eigenvalue then for each i, the ith entry of v(λ) is V_{i}(λ) which is real. Similarly the entries of w(λ) are the values of real polynomials evaluated at λ, and hence are real. Therefore the eigenvalue λ is real if and only if v(λ) is a real vector if and only if w(λ) is a real vector. □

The next lemma is a standard result.

Lemma 2.2. If λ_{i} ≠ λ_{j} then w(λ_{i})v(λ_{j}) = 0. □

With respect to the eigenvalues λ_{0}, λ_{1}, …, λ_{d} of C, we define the eigenmatrix Λ of the digraph Γ to be (d + 1) × (d + 1) matrix whose jth column is the standard eigenvector v(λ_{j}). We denote the (i, j)th entry of Λ by λ_{ij}. By the previous construction, λ_{ij} = V_{i}(λ_{j}), and the ith row of Λ consists of the eigenvalues of C_{i}. Row 0 of Λ consists of all 1s, and column 0 is v(k) = [k_{0}, k_{1}, …, k_{d}]^{T}. We prove first that Λ has at most two real columns.

Denote by K the diagonal matrix, K = diag(k_{0}, k_{1}, …, k_{d}). For each i, we have the relationship between the distance matrices A_{i^{∗}} = A_{i}^{T}. The next lemma links C_{i^{∗}}, C_{i}^{T} and K.

Lemma 2.3. For i = 0, 1, …, d, C_{i^{∗}}^{T} = K^{−1}C_{i}K.

Proof. Let h, j ∈ {0, 1, …, d, } and x be a vertex of Γ. We count in two ways the elements of the set P = {(u, v) : u ∈ Γ_{i}(x), v ∈ Γ_{j}(x) and d(u, v) = h }. For each u ∈ Γ_{i}(x) there are p_{j,h^{∗},i} = p_{h^{∗},j,i} corresponding vertices v, and for each v ∈ Γ_{j}(x) there are p_{i,h,j} = p_{h,i,j} corresponding vertices u.

Therefore |P| = k_{i}p_{h^{∗},j,i} = k_{j}p_{h,i,j}, and thus we have

(C_{h^{∗}}^{T})_{i,j} = p_{h^{∗},j,i} = k_{j}p_{h,i,j}k_{i}^{−1} = k_{j}(C_{h})_{i,j}k_{i}^{−1}.

Hence C_{i^{∗}}^{T} = K^{−1}C_{i}K. □

For each i = 0, 1, …, d, the matrices C_{i} and C_{i^{∗}} have the same set of eigenvalues and the same set of standard eigenvectors. The eigenvalues of C are distinct, and we define σ to be the permutation of {0, 1, …, d} such that λ_{dj} = λ_{1j^{σ}} (= λ_{j^{σ}}). This gives rise to a permutation of the eigenvalues of C which is in fact complex conjugation.

Lemma 2.4. For j = 0, 1, …, d, (i) for i = 0, 1, …, d, λ_{ij^{σ}} = \overline{λ}_{ij} = λ_{i^{∗}j}, and (ii) the standard right eigenvector v(\overline{λ_{j}}) = Kw(λ_{j})^{T}.

Proof. For j = 0, 1, …, d, then we have

CKw(λ_{j})^{T} = (KC_{d}^{T})w(λ_{j})^{T}
= K(w(λ_{j})C_{d})^{T}
= K(λ_{dj}w(λ_{j}))^{T}
= λ_{1j^{σ}}(Kw(λ_{j})^{T}).

Therefore Kw(λ_{j})^{T} = v(λ_{j^{σ}}), because the first entry in Kw(λ_{j})^{T} is 1. Since K is a diagonal matrix with positive diagonal entries,

w(\overline{λ}_{j})v(λ_{j^{σ}}) = \overline{w(λ_{j})}Kw(λ_{j})^{T} > 0.

Hence \overline{λ}_{j} = λ_{j^{σ}}, and thus v(\overline{λ_{j}}) = v(λ_{j^{σ}}) = Kw(λ_{j})^{T}.

Furthermore λ_{ij^{σ}} = V_{i}(λ_{j^{σ}}) = V_{i}(\overline{λ}_{j}) = \overline{V_{i}(λ_{j})} = \overline{λ}_{ij}.

Finally, for i, j ∈ {0, 1, …, d}, then

λ_{i^{∗}j}w(λ_{j}) =w(λ_{j})C_{i^{∗}}
=v(\overline{λ}_{j})^{T}K^{−1}C_{i^{∗}}
=v(\overline{λ}_{j})^{T}C_{i}^{T}K^{−1}
=(C_{i}v(\overline{λ}_{j}))^{T}K^{−1}
=λ_{ij^{σ}}v(\overline{λ}_{j})^{T}K^{−1}
=\overline{λ_{ij}}w(λ_{j})

Therefore λ_{i^{∗}j} = \overline{λ}_{ij}. □

As a corollary to this lemma we have Corollary 2.5. The eigenmatrix Λ has at most two real rows.

(i) If the girth g is odd, Λ has 1 real row, the 0th row.

(ii) If the girth g is even, Λ has 2 real rows, the 0th row and row [g/2].

Proof. The eigenmatrix is nonsingular, since its columns are the d + 1 standard eigenvectors corresponding to the d + 1 distinct eigenvalues of C. Therefore the rows are certainly distinct. However, the previous proposition shows that row i^{∗} and row i are conjugate. Therefore the ith row of Λ is real if and only if i^{∗} = i. If g is odd, then i^{∗} = i if and only if i = 0. If g is even, then i^{∗} = i if and only if i = 0 or [g/2]. □

We can now prove Theorem A.

Theorem A. Let C be the intersection matrix of a short distance-regular directed graph with girth g and valency k. Then C has g distinct eigenvalues, and

i) if g is odd, then C has exactly one real eigenvalue k, and

ii) if g is even, then C has exactly two real eigenvalues, one of which is k, and the other of which is a negative real number.

Proof. The eigenmatrix Λ is nonsingular. The permutation of the entries which takes λ_{ij} ↦ λ_{i^{∗}j} is an involution, and comes from an involutory permutation of the rows of Λ. Let L be the permutation matrix such that Λ ↦ LΛ effects this permutation of the rows. Then (LΛ)_{ij} = λ_{i^{∗}j} = \overline{λ_{ij}}.

The action on the columns of Λ, given by v(λ_{j}) ↦ v(\overline{λ_{j}}) is also an involution. Let R be the permutation matrix such that Λ ↦ ΛR effects this permutation. Then the matrix entry (ΛR)_{ij} = (v(\overline{λ_{j}}))_{i} = \overline{v(λ_{j})}_{i} = \overline{λ_{ij}} = (LΛ)_{ij}.

Therefore LΛ = ΛR, and so L = Λ^{−1}RΛ. The number of fixed points of a permutation is equal to the trace of the corresponding permutation matrix, and the traces of similar matrices are equal. Therefore L and R have the same number of fixed points in their actions.

By the previous corollary, there are at most two fixed rows, and so C has at most two real standard right eigenvectors and thus at most two real eigenvalues.

The eigenvalue λ_{0} = k is real and the nonreal eigenvalues occur in conjugate pairs. The number of eigenvalues is g. Therefore, if g is odd, then C has exactly one real eigenvalue. If g is even, then C has exactly two real eigenvalues, one of which is λ_{0} = k, and the rest are pairs of complex conjugate eigenvalues. The product of the eigenvalues is the determinant of C which can be conveniently expanded down the first column. The determinant det(C) = −k ∏_{j=o}^{d−1} C_{j,j+1}, which is −k× a product of positive integers, so the second real eigenvalue must be negative. □

Note that the argument used in the proof, that L and R have the same number of fixed points in their actions, is a special case of a combinatorial lemma due to Brauer, to be found in Feit [5].

3. Primitivity

Throughout this section Γ = (V, E) is a distance-regular digraph, not necessarily short. If the valency k = 1 then the digraph is called trivial, and in this case it is clear that it is simply a directed circuit.

Let 𝕍 = {I, E_{1}, …, E_{d}} be the partition of V^{2} defined by (x, y) ∈ E_{i} if and only if y ∈ Γ_{i}(x). For each i, we define Γ_{i} to be the digraph with vertex set V and edge set E_{i}, and so Γ_{i} is the directed graph with adjacency matrix A_{i}. If i = g/2 then Γ_{i} has girth 2. The digraphs Γ_{i} are not necessarily connected.

The digraph Γ is said to be primitive if the two trivial relations, I and V^{2}, are the only equivalence relations which are unions of members of 𝕍, otherwise Γ is called imprimitive.

Lemma 3.1. The digraph Γ is primitive if and only if each Γ_{i} is connected.

Proof. Clear. □

Lemma 3.2. (Damerell [3]) A long distance-regular digraph is imprimitive.

Proof. If Γ is a long distance-regular digraph, then E = I ∪ Γ_{g} is a nontrivial equivalence relation, so Γ is imprimitive. □

Before we complete the proof of Theorem B, we need several results concerning edges and circuits within directed shells when Γ is nontrivial.

Lemma 3.3. (Leonard and Nomura [8]). If Γ is a short and nontrivial then p_{1,1,1} > 0. That is, there are edges in the first directed shell. □

Corollary 3.4. If Γ is a short and nontrivial, and x is any vertex, then there is a closed path entirely contained in Γ_{1}(x).

Proof. Let u_{0} be any vertex in Γ_{1}(x). Choose u_{1} to be any out-neighbour of u_{0} in Γ_{1}(x). Choose u_{2} to be any out-neighbour of u_{1} in Γ_{1}(x). Continue in this way constructing a path u_{0}, u_{1}, … u_{j} in Γ_{1}(x). Since Γ_{1}(x) is finite, for some smallest m, u_{m} = u_{h} for some h < m. Then u_{h} ⟶ u_{h+1} ⟶ u_{h+2} ⟶ ⋯ ⟶ u_{m} = u_{h} is a closed path with all u_{j} in Γ_{1}(x). □

As a further corollary we have that in the first directed shell of any vertex there are vertices y and z with d(y, z) = j for any j ≤ d, that is the entries in column 1 of C are all nonzero.

Corollary 3.5. If Γ is a short and nontrivial then p_{1,i,1} > 0 for i = 0, 1, …, d. □

Corollary 3.6. If Γ is a short and nontrivial then p_{d,1,i} > 0 for i = 0, 1, …, d. □

Proof. Let x, y, z be vertices with d(x, y) = 1, d(y, z) = i^{∗} and d(x, z) = 1. These exist since p_{1,i^{∗},1} > 0. Then d(z, x) = 1^{∗} = d, d(x, y) = 1 and d(z, y) = (i^{∗})^{∗} = i. Therefore p_{d,1,i} > 0. □

Lemma 3.7. If Γ is a short nontrivial distance-regular digraph, and 0 < i ≤ \frac{g}{2}, x ∈ V and y ∈ Γ_{i}(x), then there is a vertex z ∈ Γ_{i}(x) such that 0 < d(y, z) < i.

Proof. Let 0 < i ≤ \frac{g}{2}. We use the commutativity of the intersection matrices, and in particular (C_{1}C_{d})_{1i} = (C_{d}C_{1})_{1i}.

(C_{1}C_{d})_{1i} = ∑_{j=0}^{d} p_{1,1,j}p_{d,j,i} = p_{1,1,1}p_{d,1,i} + p_{1,1,2}p_{d,2,i}.

(C_{d}C_{1})_{1i} = ∑_{j=0}^{d} p_{d,1,j}p_{1,j,i} = p_{d,1,i−1}p_{1,i−1,i} + p_{d,1,i}p_{1,i+1,i} ⋯ + p_{d,1,d}p_{1,d,i}.

Now p_{1,1,1} = p_{d,1,d} and p_{d,1,i} = p_{1,d,i}. Therefore p_{1,1,2}p_{d,2,i} ≥ p_{d,1,i−1}p_{1,i−1,i} > 0, and so p_{d,2,i} > 0. Therefore there are edges from Γ_{i}(x) to Γ_{2}(x).

Now suppose y ∈ Γ_{i}(x). Since p_{d,2,i} > 0, there exists a w in Γ_{2}(x) ∩ Γ_{1}(y). Since w ∈ Γ_{2}(x), there exists z ∈ Γ_{i}(x), with d(w, z) = i − 2.

Therefore d(y, z) ≤ d(y, w) + d(w, z) = i − 1 < i. □

Setting i = 2 in this lemma we have that there are edges in the second directed shell.

Corollary 3.8. If Γ is short and nontrivial then p_{1,2,2} > 0. □

Corollary 3.9. If Γ is short and nontrivial, and x is any vertex, then there is a closed path entirely contained in Γ_{2}(x). □

We can now prove Theorem B.

Theorem B. Let Γ be a short distance-regular directed graph with valency k and n vertices.

i) If k = 1 then Γ is a directed circuit with n vertices and is primitive if and only if n is prime.

ii) If k > 1 then Γ is primitive.

Proof.

i) If k = 1 then Γ is a directed circuit with n vertices. Clearly in this case Γ is primitive if and only if n is prime.

ii) Suppose k > 1 and that E is an equivalence relation on V which is a union of members of 𝕍. Then for some ℓ, a divisor of g, E = I ∪ E_{ℓ} ∪ E_{2ℓ} ∪ ⋯ ∪ E_{g−ℓ}. Any two vertices y and z are in the same equivalence class if and only if ℓ divides d(y, z).

Suppose 1 < ℓ ≤ \frac{g}{2}, and x ∈ V. The equivalence class containing x also contains Γ_{ℓ}(x). By the previous lemma there are y, z ∈ Γ_{ℓ}(x) such that 0 < d(y, z) < ℓ. However, since y and z are in the same equivalence class ℓ divides d(y, z). This is a contradiction, and so ℓ = 1 and the equivalence relation is trivial.

Therefore any short nontrivial distance-regular digraph is primitive. □

A group G which acts transitively on a set acts primitively if the only partitions of the set which it preserves are the trivial ones, and so the corollary follows immediately.

Corollary. Let Γ be a short distance-regular directed graph with valency k > 1. Then any distance-transitive group of automorphisms acts primitively on the vertices.

References

1. E. Bannai and P.J. Cameron and J. Kahn, Nonexistence of certain distancetransitive digraphs, J. Combinatorial Theory, Ser. B 31 (1981), 105-110.

2. D.Combe, Distance-transitive directed graphs and multiplicity free primitive permutation representations with almost no real irreducible constituents, PhD thesis, University of Sydney, 1998.

3. R.M. Damerell, Distance-transitive digraphs, J. Combinatorial Theory, Ser. B 31 (1981), 46-53.

4. H. Enomoto and R.A. Mena, Distance-regular digraphs of girth 4, J. Combinatorial Theory, Ser. B 43 (1987), 293-302.

5. W. Feit, Characters of Finite Groups, W.A.Benjamin, Inc. Amsterdam., 1967.

6. W.M. Kantor, Automorphism groups of designs, Math. Z. 109 (1967), 246-252.

7. C.W.H. Lam, Distance-transitive digraphs, Discrete Math. 9 (1980), 265–274.

8. D.A. Leonard and K. Nomura, The girth of a directed distance-regular graph, J. Combinatorial Theory, Ser. B 58 (1993), 34-39.

9. R.A. Liebler and R.A. Mena, Certain distance-regular digraphs and related rings of characteristic 4, J. Combinatorial Theory, Ser. A 47 (1988), 111-123.

10. T. Takashi, Distance-regular digraphs of girth 6, Mem. Fac. Sci., Kyushu Univ., Ser. A 45 (1991), 155-166.

11. M. Yamada, Distance regular digraphs of girth 4 over an extension ring of ℤ/4ℤ, Graphs and Combinatorics 6 (1990), 381-394.

D. Combe School of Mathematics and Statistics University of Sydney N.S.W. 2006 Australia.

 E-mail address: dianac@maths.usyd.edu.au

D. E. Taylor School of Mathematics and Statistics University of Sydney N.S.W. 2006 Australia.

 E-mail address: don@maths.usyd.edu.au