Weakly Distance-Regular Digraphs

F. Comellas¹, M. A. Fiol, J. Gimbert², and M. Mitjana³

September 9, 2002

Running Head:
weak distance-regularity

Mailing Address:
M.A. Fiol
Departament de Matemàtica Aplicada IV
Universitat Politècnica de Catalunya
Jordi Girona 1-3
Mòdul C3, Campus Nord
08034 Barcelona, SPAIN.

Email:
fiol@mat.upc.es

Abstract

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented.

1 Introduction

Let us first introduce some basic notation (see [4,17]) and discuss the relevant background. Let G =(V,E) be a (strongly) connected digraph with order N:=|V| and diameter D. We will denote by dist (u,v) the distance from vertex u to vertex v. Notice that dist (u,v) and dist (v,u) may not be equal since we are considering oriented graphs. For any fixed integer 0 Ł k Ł D, we will denote by G⁺_k(v) (respectively, G^-_k(v)) the set of vertices at distance k from v (respectively, the set of vertices from which v is at distance k). Sometimes it is written, for short, G⁺(v) or G^-(v) instead of G₁⁺(v) or G₁^-(v), respectively. Thus, the out-degree and in-degree of v are d⁺(v):=|G⁺(v)| and d^-(v):=|G^-(v)|; and the digraph G is (D-)regular if d⁺(v)=d^-(v)=D for every v Î V.

Distance-transitivity and distance-regularity

The concept of a distance-regular digraph was introduced by Damerell [9] in the late seventies. He defined distance-regular digraphs by using a regularity type condition concerning the cardinality of some vertex subsets. More precisely, a digraph G with diameter D is distance-regular if, for any pair of vertices u,v Î V such that dist (u,v)=k, 0 Ł k Ł D, the numbers

s_i1^k(u,v):=|G_i⁺ (u)ÇG₁⁺ (v)|,

(1)

for each i such that 0 Ł i Ł k+1, do not depend on the chosen vertices u and v, but only on their distance k. In this case, we just write s_i1^k and refer to them as the intersection numbers. (According to Damerell's notation [9], s_i1^k would be just s_ik.) As happens in the undirected case, the notion of distance-regularity in digraphs can be seen as a generalization of the concept of distance-transitivity. The concept of distance-transitive digraphs was introduced by Lam in [19] as a natural generalization of distance-transitive graphs. A digraph G is said to be distance-transitive if for all vertices u,v,x,y such that dist (u,v)= dist (x,y) there is an automorphism p of G such that p(u)=x and p(v)=y. That paper provided some examples of distance-transitive digraphs with girth g and diameter D=g-1, as the directed cycle and the Paley tournament, and presented a method to construct more distance-transitive digraphs, with D=g, starting from a distance-transitive digraph with D=g-1. Damerell [9] proved that every distance-transitive digraph G with girth g, say, is stable; that is, dist (u,v)+ dist (v,u)=g for any pair of vertices u,v Î V(G) at distance 0 < dist (u,v) < g. (Thus, a stable digraph of girth two can be identified with the graph obtained by replacing each pair of opposite arcs, or `digon', by an undirected edge.) Consequently, every distance-transitive digraph has diameter D=g (`long' distance-transitive digraph ) or D=g-1 ( `short' distance-transitive digraph ), provided that g ł 3. Moreover, Damerell showed that the classification of these digraphs can be reduced to the case g=D+1 (i.e., the short digraphs) since every long digraph is obtained from a short digraph, with the same girth, by the construction described by Lam. Using these results, Bannai, Cameron and Kahn [1] proved that the distance-transitive digraphs given by Lam were the only ones with odd girth.

The above results were extended by Damerell to the case of distance-regular digraphs. He also gave the classification in `short' and `long' digraphs, and the structure of the long digraphs. Taking into account that the case g=2 corresponds to the distance-regular graphs, the study of the distance-regular digraphs is reduced to the case g ł 3 (and g=D+1). In particular, there is a correspondence between the distance-regular digraphs with girth g=3 and diameter D=2 and the so-called skew Hadamard matrices . For g=4,5,6, there are some works where the intersection numbers are computed by using the smallest number of defining parameters (see e.g. Enomoto and Mena [12] and Liebler and Mena [21]). Finally, Douglas and Nomura [10] showed that the girth g of a distance-regular digraph with degree D > 1 and diameter D always satisfies D Ł g Ł 8.

If we change G₁⁺(v) to G₁^-(v) in the definition of distance-regularity, we get some new parameters p_i1^k, called again the intersection numbers. But now the stability property does not necessarily hold, and a class of digraphs with less structure appears. We focus our attention on such digraphs, here referred to as `weakly distance-regular', and study some of their properties, which are closely related to the properties enjoyed by the distance-regular digraphs. In fact, the diameter 2 weakly distance-regular digraphs are the same as the `directed strongly regular graphs' introduced by Duval [11], which have recently been studied by a number of authors and found several constructions, see [5]. In our more general context, and besides several characterizations given in the next section, it is shown that every (standard) distance-regular digraph is also weakly distance-regular, so justifying the name. In this case, the relationship between the defining parameters, s_i1^k and p_i1^k, shows to be very simple. Subsequently, we devote Section 4 to the study of the spectra of weakly distance-regular digraphs, providing formulas for computing the eigenvalue multiplicities from the entries of some different `small' matrices. Finally, some constructions and specific families of weakly distance-regular digraphs, which are interesting for their applications in network theory, are analyzed.

Since most of our study is of an algebraic nature, we next recall some background from algebraic graph theory and matrix theory. The adjacency matrix A =(a_uv) of a digraph G (we assume⁴ that G contains neither loops nor multiple edges) is the N×N matrix indexed by the vertices of G, with entries a_uv = 1 if u is adjacent to v, and a_uv = 0 otherwise. The spectrum of the digraph G, denoted by sp G, consists of the eigenvalues of A, which might be not real since A is not symmetric, together with their (algebraic) multiplicities.

sp G={l₀^m(l₀),l₁^m(l₁),...,l_d^m(l_d)}.

The distance-k matrix A_k of a digraph G with diameter D, where 0 Ł k Ł D, is defined by

(A_k)_uv: =

ě
í
î

if dist (u,v)=k,

otherwise.

(2)

In particular, A₀=I and A₁=A. As we will see, these matrices play a key role in the study of distance-regularity. For instance, it is known that a digraph G is distance-regular (in the sense of Damerell) if and only if the set of matrices {A_k}_k=0^D satisfies the axioms of a commutative association scheme; see Takahashi [26]. (The readers who are not familiar with association schemes can consult, for instance, Godsil's textbook [17].) This important result is going to be used later.

Some other basic results from algebraic graph theory are the following:

By the Perron-Frobenius theorem, the maximum eigenvalue l₀ of G is simple and has a positive eigenvector n. In particular, if G is D-regular, then n =j, where j denotes the all-1 vector, and l₀=D.
The number of walks of length l ł 0 from vertex u to vertex v is equal to a_uv^(l):=(A^l)_uv.
The adjacency algebra of G (also called Bose-Mesner algebra when it is closed under the Hadamard-or componentwise-product) is defined by

A(G):={p(A) : p Î \mathbbC[x]},

where A is the adjacency matrix of G. The dimension of A(G), as a \mathbbC-vector space, equals the degree of the minimum polynomial m_G of G, and it is at least D+1 since the powers I,A,Ľ,A^D are linearly independent.
A digraph G is (strongly) connected and regular if and only if there is a polynomial p Î \mathbbQ[x] such that p(A)=J, where J denotes the all-1 matrix (see [6], Th. 5.3.1). The polynomial H_G of least degree satisfying this property is called the Hoffman polynomial of G and it is given by

H_G:= N
S(D)
S,
(3)
where m_G:=(x-D)S Î \mathbbZ[x] is the minimum polynomial of G.

We end this introductory section by recalling some results from matrix theory (see e.g. [20]). Given a complex matrix A, we denote by A^* the transpose of its conjugate. Thus, A is hermitian if A^*=A, and it is unitary when AA^*=I. Moreover, A is said to be normal if AA^*=A^*A. The following result summarizes several characterizations of normal matrices.

Theorem 1 Let A be an n×n complex matrix with eigenvalues q₁,q₂,Ľ,q_n. Then A is normal if and only if any of the following assertions hold:

$(a)$ A diagonalizes by means of a unitary matrix; that is, U^*AU =D for some matrix U such that UU^*=I, and D:= diag (q₁,q₂,Ľ,q_n).
$(b)$ A^*=p(A) for some polynomial p Î \mathbbC[x].
$(c)$ tr (AA^*)=ĺ_i=1ⁿ|q_i|².

Note that, from (a), the eigenvectors of a normal n×n square matrix constitute an orthogonal basis of the vector space \mathbbCⁿ, with the Hermitian scalar product áu,vń_*:=u^T[`(v)]. Let us now assume that A has distinct eigenvalues l₀,l₁,Ľ,l_d. For each l_i, let U_i be the matrix whose columns form an orthonormal basis of the eigenspace E_i:= Ker (A-l_iI). Then the orthogonal projection onto E_i is represented by the matrix E_i:=U_iU_i^* or, alternatively,

E_i=

f_i

Ő
j ą i

(A-l_jI) (0 Ł i Ł d),

(4)

where f_i:=Ő_{j=0(j ą i)}^d(l_i-l_j). These (hermitian) matrices are called the (principal ) idempotents of A, and satisfy the following properties: E_iE_j=d_ijE_i; AE_i=l_iE_i; sp E_i={1^m(l_i),0^n-m(l_i)}; and, for every rational function f defined at each l_i, 0 Ł i Ł d,

f(A)=

d
ĺ
i=0

f(l_i)E_i.

(5)

In particular, when f=x, the above equation becomes the so-called spectral decomposition theorem: A =ĺ_i=0^d l_iE_i.

2 Weak distance-regularity

We begin this section by formally introducing the concept of weakly distance-regular digraph, through the invariance of the number of walks between vertices at a given distance. (This approach has already been used to characterize distance-regular graphs, see e.g. Rowlinson [25].) Afterwards, and as already mentioned, we will show that this concept is equivalent to change G₁⁺(v) to G₁^-(v) in the definition of a distance-regular digraph.

Definition 1 A digraph G of diameter D is weakly distance-regular if, for each non-negative integer l Ł D, the number a_uv^(l) of walks of length l from vertex u to vertex v only depends on their distance dist (u,v)=k, for any l = 0,1,..., D. In this case we write a_uv^(l)=a_k^l for some constants a_k^l, 0 Ł k, l Ł D.
Of course a_k^l=0 for any k > l, since there is no walk of length l between vertices u,v at distance dist (u,v) > l. Moreover, if the digraph is geodetic (that is, the shortest path between any two vertices is unique), then a_k^k=1 for any 0 Ł k Ł D.

>From the definition of G as a weakly distance-regular digraph , it follows that each matrix power A^l, 0 Ł l Ł D, can be expressed as a linear combination of the distance matrices A₀,A₁,...,A_D which, as we will see next, belong to the adjacency algebra of G. The following theorem provides some characterizations of weakly distance-regular digraphs which are analogous to those applying for distance-regular graphs (for a survey of the latter, see e.g. [15]).

Theorem 2 Let G be a connected digraph with diameter D and distance matrices {A_k}_k=0^D. Then, the following are equivalent:

$(w)$ G is a weakly distance-regular digraph.
$(a)$ The distance matrix A_k is a polynomial of degree k in the adjacency matrix A; that is, A_k=p_k(A), for each k=0,1, ..., D, where p_k Î \mathbbQ[x].
$(b)$ The set of distance matrices {A_k}_k=0^D is a basis of the adjacency algebra A(G).
$(c)$ For any two vertices u,v Î V(G) at distance dist (u,v)=k, the numbers

p_ij^k(u,v):=|G_i⁺ (u)ÇG_j^- (v)|
(6)
do not depend on the vertices u and v, but only on their distance k; in which case they are denoted by p_ij^k (note that p_ij^k=0 when k > i+j).

Proof. (w)Ű (a) If G is weakly distance-regular, the number of walks of length l Ł D from vertices u,v at distance k is a_uv^(l)=a_k^l (a constant). Hence,

A^l = a₀^lI+a₁^lA+a₂^lA₂+...+a_l^lA_l (0 Ł l Ł D)

(7)

where, necessarily, a_l^l ą 0 and, as already mentioned, a_k^l=0 for any k > l. In matrix form,

ć
ç
ç
ç
ç
ç
ç
č

A²

A^D

ö
÷
÷
÷
÷
÷
÷
ř

ć
ç
ç
ç
ç
ç
ç
č

a₀⁰

a₀¹

a₁¹

a₀²

a₁²

a₂²

a₀^D

a₁^D

a_D^D

ö
÷
÷
÷
÷
÷
÷
ř

ć
ç
ç
ç
ç
ç
ç
č

A₂

A_D

ö
÷
÷
÷
÷
÷
÷
ř

(8)

where C:=(a_k^l) is a lower triangular matrix. Since a_l^l > 0 for any 0 Ł l Ł D, the matrix C is non-singular and its inverse C^-1 is also a lower triangular matrix. Hence A_k is a polynomial of degree k in A:

A_k=p_k(A)=a₀^kI+a₁^kA+a₂^kA²+...+a_k^kA^k (0 Ł k Ł D),

(9)

where a_k^k ą 0. Conversely, let us assume that there are constants a_l^k, with a_k^k ą 0, satisfying (9). This implies that Eqs. (7) and (8) also hold with C =(a_k^l) being the inverse matrix of C^-1=(a_l^k) and, hence, the number of walks of length l Ł D from one vertex to another only depends on their distance.

(a)Ţ (b) We know that {I,A,...,A_D} constitutes a set of linearly independent matrices of the adjacency algebra A(G). Moreover, since A_k=p_k(A) and ĺ_k=0^D A_k=J, it follows that H(A)=J, where H:=ĺ_k=0^D p_k. As a consequence, G is a regular digraph of degree D, say. Furthermore, since the minimum polynomial m_G of G divides (x-D)H we have D+1 Ł dimA(G) = dgr m_G Ł D+1. Hence, the dimension of A(G) attains the minimum value allowed by the diameter, dimA(G)=D+1, and both {A^l}_l=0^D and {A_k}_k=0^D are bases of A(G).

(b)Ţ (c) Let u and v be two vertices of the digraph G, such that dist (u,v)=k. Notice that the number p_ij^k(u,v), representing the number of vertices at distance i from u and at distance j to v, coincides with the (u,v)-entry of the matrix A_iA_j which, because of (b), is a linear combination of the basis {A_k}_k=0^D, say,

A_iA_j=

D
ĺ
k=0

g_ij^k A_k.

(10)

Consequently, p_ij^k(u,v)=g_ij^k=p_ij^k for any two vertices u,v at distance k.

(c)Ţ (a) If (10) holds for j=1:

A_iA₁=

D
ĺ
k=0

p_i1^k A_k (0 Ł i Ł D),

(11)

we can use an inductive argument, starting from A₀=I and A₁=A, to deduce that the distance matrix A_k is indeed a polynomial of degree k in the adjacency matrix A. ^[¯]

>From now on, the polynomials p_k such that A_k=p_k(A), 0 Ł k Ł D, will be referred to as the distance polynomials of G. Notice that, from (b), any matrix power A^l is a linear combination of the distance matrices and, consequently, the number a_uv^(l) of walks of any fixed length l ł 0 between vertices u,v of G only depends on their distance. Other interesting consequences of the above theorem are the following.

Corollary 3 Let G be a weakly distance-regular digraph on N vertices, with diameter D, adjacency matrix A, and distance polynomials {p_k}_k=0^D. Then,

$(i)$ The Hoffman polynomial of G is H_G=ĺ_k=0^Dp_k. In particular, G is a regular digraph of degree D, where ĺ_k=0^D p_k(D)=N. Moreover, the minimum polynomial of G is m_G=(x-D)[ 1/(a_D^D)]H_G, where a_D^D is the leading coefficient of p_D.
$(ii)$ The number n_k of vertices at distance k from any given vertex is equal to p_k(D), for each k=0,1,...,D.
$(iii)$ The spectrum of G is uniquely determined by the entries of the (D+1)×(D+1) matrix C =(a_k^l).

Proof. (i)-(ii) From the proof of Theorem 2.2(b), we see that H_G=H=ĺ_k=0^D p_k, G is a D-regular digraph, and the minimum polynomial m_G is as claimed. Moreover, we have that j =(1,1,... ,1)^T is an eigenvector of A corresponding to the eigenvalue D. Consequently, A_kj =p_k(A)j =p_k(D)j, which implies that H_G(D)=ĺ_k=0^Dp_k(D)=N, in concordance with (3).

(iii) This follows from the fact that the characteristic polynomial of G is uniquely determined by the minimum polynomial m_G and the spectral invariants tr A^l=N a₀^l, 0 Ł l Ł D (see Section 3 for more details). ^[¯]

As we will see, in the case of weakly distance-regularity, the average of the intersection numbers (1) also play a role. In a given digraph with diameter D, let N_k, 0 Ł k Ł D, denote the number of (ordered) vertex pairs u,v such that dist (u,v)=k; that is, N_k:=ĺ_{u Î V} n_k(u). Thus, N₀=N and N₁=|E|. Then the mean intersection numbers [`s]_i1^k are defined by

k
i1

N_k

ĺ
dist (u,v)=k

s_i1^k(u,v)

(12)

and, more generally, we define [`s]_ij^k as the average of the numbers s_ij^k(u,v):=|G_i⁺(u)ÇG_j⁺(v)|.

To see what is the significance of these parameters, let us consider, for a given digraph G with adjacency matrix A, the following scalar product in \mathbbC[x]:

áf,gń_G:=

tr (f(A)g(A)^*).

(13)

In fact, notice that this product is well defined in the quotient ring \mathbbC[x]/Á, where Á:=(m_G) is the ideal generated by the minimum polynomial of G. This is due to the additive property of the trace and tr (m_G(A))= tr Ø = 0.

Then, if G is a weakly distance-regular digraph, its distance polynomials are orthogonal with respect to this product. Indeed,

áp_k,p_lń_G=

tr (A_kA_l^T) =

ĺ
u Î V

|G_k⁺(u)ÇG_l⁺(u) |=0 (k ą l),

(14)

and

||p_k||_G²=

tr (A_kA_k^T)=n_k=p_k(D).

(15)

Consequently, the set {p_k}_k=0^D is a basis of the quotient ring \mathbbC[x]/Á, which is isomorphic to A(G). The representation of p_ix in terms of such a basis must be of the form

p_ix =

D
ĺ
k=0

g_i^k p_k (0 Ł i Ł D)

where g_i^k is the corresponding Fourier coefficient. Comparing with (11), we conclude that g_i^k must be equal to the intersection number p_i1^k (a real number). Hence,

g_i^k=

g_i^k

áp_ix,p_kń_G

||p_k||_G²

áp_k,p_ixń_G

||p_k||²_G

(0 Ł i Ł D)).

(16)

In the following result we show that these Fourier coefficients can also be computed from the average intersection numbers [`s]_ij^k.

Proposition 4 The coefficients of the above recurrence satisfied by the distance polynomials of a weakly distance-regular digraph are:

g_i^k = p_i1^k= N_i
N_k

s

i
k1
.

Proof. If we compute g_i^k by using the first expression in (16), we get

g_i^k

áp_ix,p_kń_G

||p_k||_G²

tr (A_iAA_k^T)

tr (A_kA_k^T)

ĺ
u Î V

ĺ
v Î V

(A_i)_uv(AA_k^T)_vu

ĺ
u Î V

ĺ
v Î V

(A_k)_uv(A_k)_uv

N_k

ĺ
u Î V

ĺ
v Î G_i⁺(u)

(AA_k^T)_vu =

N_k

ĺ
u Î V

ĺ
v Î G_i⁺(u)

(A_kA^T)_uv

N_k

ĺ
u Î V

ĺ
v Î G_i⁺(u)

s_k1ⁱ(u,v) =

N_i

N_k

i
k1

This completes the proof, as we already know that g_i^k=p_i1^k (in fact, this is what we get if we compute g_i^k by using the second expression in (16)). ^[¯]

In general, as a consequence of Theorem 2.2 and áp_k,p_ip_jń_G=áp_ip_j,p_kń_G, we reach the following conclusion:

Corollary 5 A distance-regular digraph G with intersection numbers s_ij^k is also a weakly distance-regular digraph with intersection parameters p_ij^k satisfying

N_k p_ij^k=N_i s_kjⁱ.
(17)

Proof. Since G is distance-regular, its adjacency algebra is a (P-polynomial) association scheme (that is, each distance matrix A_k, 0 Ł k Ł D, is a polynomial p_k of degree k in A) and so Theorem 2.2(a) applies. This assures that the numbers p_ij^k exist and the proof goes as before. (In fact, notice that (17) just counts in two ways the number of ordered triples (x,y,z) such that dist (x,y)=k, dist (x,z)=i, and dist (z,y)=j.) ^[¯]

Thus, any distance-regular digraph G satisfies all the above properties of weakly distance-regular digraphs. Moreover, since G is stable and has girth g Î {2,D,D+1}, see [9], we have

AA^T=AA_g-1=Ap_g-1(A)=A_g-1A=A^TA

(since 1 Ł g-1 Ł D) and A is a normal matrix.

As a consequence of the above, we now have the following characterization result, showing that the (standard) distance-regular digraphs are precisely those weakly distance-regular digraphs which are stable or have a normal adjacency matrix.

Proposition 6 Let G be a weakly distance-regular digraph with adjacency matrix A. Then G is distance-regular if and only if any of the following conditions hold:

$(a)$ G is stable.
$(b)$ A is normal.

Proof. We only need to prove that each of the conditions is sufficient.

(a) Let G be a weakly distance-regular digraph with diameter D. From the proof of Theorem 2.2, we already know that A_iA_j=A_jA_i is a linear combination of the basis {A_k}_k=0^D, see (10). On the other hand, since G is stable, we have that A_k^T=A_g-k, 0 < k < g, where g is the girth of G. If g=2, then G is a symmetric digraph since A^T = A and, consequently, A_k^T = A_k for each k=0,1,...,D. If g ł 3, then g=D or g=D+1 (see [9,Theorem 2]), which implies that A_k^T = A_D-k (0 < k < D) and A_D^T = A_D, if g=D, and A_k^T = A_D+1-k, if g=D+1 and 0 < k Ł D. Thus, the adjacency algebra A(G) is closed under the "transposition operation". Hence, the set of matrices {A_k}_k=0^D satisfies the axioms of a (commutative) association scheme and G is a distance-regular digraph.

(b) If A is normal, then by Theorem 1.1(b) there exists a polynomial p Î \mathbbC[x] such that A^T=p(A). Thus, A_iA^T Î A(G) and, hence, it admits a representation in terms of the basis {A_k}_k=0^D, which must be of the form

A_iA^T=

D
ĺ
k=0

s_i^kA_k (0 Ł i Ł D)

since (A_iA^T)_uv=|G_i⁺(u)ÇG⁺(v)|. Therefore, as the Fourier coefficients s_i^k only depend on k (and i), they coincide with the intersection numbers s_i1^k and G is distance-regular. ^[¯]

>From this result, we can see now that the scalar product associated to a distance-regular digraph has a simple expression in terms of its spectrum sp G ={l₀^m(l₀),l₁^m(l₁),...,l_d^m(l_d)}. Indeed, using Theorem 1.1 and the properties of the idempotents, (13) becomes

áf,gń_G=

d
ĺ
i=0

f(l_i)

g(l_i)

tr (E_iE_i^*) =

d
ĺ
i=0

m(l_i) f(l_i)

g(l_i)

(18)

which, except for the conjugation, is like the scalar product used for distance-regular graphs (see [15]). In the next section, we will derive the corresponding expression for a weak distance-regular digraph.

3 The spectrum and the condensed matrices

In this section we study how to compute the spectrum of a weakly distance-regular digraph in terms of its defining parameters. We will see that the whole spectrum of such a digraph can be retrieved from the information given by some specific matrices characterizing it, such as the recurrence matrix or the multiplicity matrix, which have size much more smaller than the adjacency matrix. Thus, these matrices are here generically referred to as the `condensed matrices'.

The multiplicities

First recall that, by Corollary 2.3(i), the distinct eigenvalues of a weakly distance-regular digraph G with distance polynomials {p_k}_k=0^D are l₀=D and the different zeros l₁,l₂,Ľ,l_d (d Ł D) of its Hoffman polynomial H_G=ĺ_k=0^D p_k. Moreover, their respective multiplicities can be computed by solving the system of linear equations

tr A^j=

d
ĺ
i=0

m(l_i)l_i^j = N a₀^j (0 Ł j Ł d),

(19)

where the independent terms a₀^j=a_uu^(j) can be computed from the coefficients of the distance polynomials (see the proof of Theorem 2.2); and the coefficient matrix is a Vandermonde matrix formed from the distinct values l₀,l₁,Ľ,l_d.

However, in our context, a more direct way of computing the multiplicities is to consider the traces of the distance matrices. Indeed, since

tr A_i= tr (p_i(A))=

d
ĺ
j=0

m(l_j)p_i(l_j)=d_0i N (0 Ł i Ł d)

(20)

(notice that tr A_i=Náp_i,p₀ń_G) we have the following result:

Proposition 1 Let G be a weakly distance-regular digraph with N vertices, distance polynomials {p_k}_k=0^D, and distinct eigenvalues l₀(=D),l₁,Ľ,l_d. Let ¶_ev be the matrix whose (i,j)-element is p_i(l_j), 0 Ł i,j Ł d. Then the multiplicities m(l_i) are given by

m(l_i)=N(¶_ev^-1)_i0 (0 Ł i Ł d).
(21)

Proof. Since ¶_ev is clearly non-singular, (20) yields

ć
ç
ç
ç
č

m(l₀)

m(l₁)

m(l_d)

ö
÷
÷
÷
ř

ć
ç
ç
ç
č

p₀(l₀)

p₀(l₁)

...

p₀(l_d)

p₁(l₀)

p₁(l₁)

...

p₁(l_d)

p_d(l₀)

p_d(l₁)

...

p_d(l_d)

ö
÷
÷
÷
ř

-1

ć
ç
ç
ç
č

ö
÷
÷
÷
ř

(22)

which corresponds to (21). ^[¯] In the following subsections we study other matrices related to G, which also contain the information about its multiplicities. We begin with a positive definite matrix which gives an alternative expression for the scalar product (13).

The multiplicity matrix

Let G be a weakly distance-regular digraph with diameter D, and adjacency matrix A with distinct eigenvalues l₀(=D),l₁,Ľ,l_d, where d Ł D. Let m₀,m₁,Ľ,m_d denote the multiplicities of such eigenvalues, as zeros of the minimum polynomial m_G. Thus, m₀=1, 1 Ł m_i Ł m(l_i) for any 1 Ł i Ł d, and ĺ_i=0^d m_i=D+1. For every polynomial f Î \mathbbC[x], let us define the (row) vector f =(f₀,f₁,Ľ,f_D) Î \mathbbC^D+1 as

f:=

ć
č

f(l₀),f(l₁),f˘(l₁),

f"(l₁)

,Ľ,

f^(m₁-1)(l₁)

(m₁-1)!

,Ľ,f(l_d),f˘(l_d),Ľ,

f^(m_d-1)(l_d)

(m_d-1)!

ö
ř

where the superscripts stand for the orders of the derivatives. Then we claim that there exists a positive definite matrix M =(m_rs), 0 Ł r,s Ł D, such that the scalar product (13) can be written as

áf,gń_G=

fMg^* =

D
ĺ
r,s=0

m_rs f_r

g_s

(23)

Moreover, the row (or column) sums of a given submatrix M_ev of M yield the multiplicities of G. More precisely let us consider the set of indexes J:={0,ĺ_j=0^i-1 m_j: 1 Ł i Ł d} Í \mathbbZ_D+1, and let M_ev denote the principal submatrix of M whose row and column indexes are the (d+1) elements of J. Then

d
ĺ
j=0

(M_ev)_ij = m(l_i) (0 Ł i Ł d).

Since the distance polynomials form a basis, to prove the first statement it is enough to show that there is a matrix M satisfying (14) and (15); that is, [ 1/N]p_kMp_l^*=d_klp_k(D) or, in matrix form,

PM¶^*=D

where ¶ is the matrix with rows p₀,p₁,Ľ,p_D and D:= diag (p₀(D),p₁(D),Ľ,p_D(D)). Thus, since the vectors p₀,p₁,Ľ,p_D are linearly independent (otherwise, Hermite interpolation at l₀,l₁,Ľ,l_d would give a contradiction) the matrix ¶ has an inverse and so

M=N¶^-1D(¶^-1)^*=VV^*

(24)

where we have introduced the new (nonsingular) matrix V:=ÖN¶^-1D^1/2. Hence, M is a definite positive hermitian matrix (note that, for any f ą 0, fMf^*=||f||_G² > 0).

Furthermore,

tr A_k=

d
ĺ
i=0

p_k(l_i)m(l_i)=p_km^* (0 Ł k Ł D),

(25)

where m is a (D+1)-vector whose r_i-th entry is m(l_i), when r_i Î J is defined as r₀:=0 and r_i:=m₀+m₁+Ľ+m_i-1, 1 Ł i Ł d; and m_r=0 if r Ď J. Also,

tr A_k=Náp_k, p₀ń_G=p_kMp₀^* (0 Ł k Ł D).

(26)

Thus, by (25) and (26),

p_k(Mp₀^*-m^*)=0 (0 Ł k Ł D)

and, by the independence of p₀,p₁,Ľ,p_D, we conclude that Mp₀^*=m^*, and hence M_evj = m_ev^* where m_ev:=(m(l₀),m(l₁),Ľ,m(l_d)). Of course, this gives a way of computing the multiplicities from the entries of M which, in turn, can be computed from the distance polynomials using (24). This gives:

m^*

Mp₀^*=N¶^-1D(¶^-1)^*p₀^* = N¶^-1D(p₀¶^-1)^*

N¶^-1e₁^*

(27)

where e₁ is the 1-th coordinate vector. Consequently, m^* is just N times the first column of ¶^-1. (A result to be compared with (22) which, with the above notation, reads m_ev^*=N¶_ev^-1e₁^*.) A more direct way of seeing this is to consider again (25). Indeed, as tr A₀=N and tr A_k=0 for any 1 Ł k Ł D, Eqs. (25) yield, in matrix form, ¶m^*=Ne₁^*, whence (27) follows.

Let us now prove that m_0s = 0 for any s ą 0 and m₀₀=1. To this end, we now compute the scalar product áZ_ie,H_Gń_G, where Z_ie: = m_G/(x-l_i)^e, 1 Ł e Ł m_i, in two different ways:

áZ_ie,H_Gń_G=

tr (Z_ie(A)H_G(A)^*) =

tr (Z_ie H_G(A)) =

ě
í
î

if i ą 0

Z₀₁(D)

if i=0

(28)

since H_G=[ N/(Z₀₁(D))] Z₀₁ and hence Z_ie H_G is a multiple of m_G for any i ą 0. Also, from the vectors Z_ie = (0,0,Ľ,0,Z^(m_i-e)_ie(l_i),Ľ,Z_ie^(m_i-1)(l_i),0,Ľ,0) and H_G=(N,0,0,Ľ, 0) (derived from the respective polynomials), we have

áZ_ie,H_Gń_G=

r_i+m_i-1
ĺ
r=r_i+m_i-e

m_r0(Z_ie)_r(H_G)₀ =

r_i+m_i-1
ĺ
r=r_i+m_i-e

m_r0Z_ie^(r-r_i)(l_i).

(29)

Thus, equating (28) and (29) for i=0 (whence r₀=0 and e = 1) we get m₀₀=1. Similarly, for i ą 0 and e = 1, we obtain m_r0Z_ie^(m_i-1)(l_i)=0 where r=r_i+m_i-1. Hence, for such a value of r, we must have m_r0=0, as Z_ie^(m_i-1)(l_i) ą 0. Recursively, for the same i and e = 2,Ľ, m_i-1 we obtain m_r0=0 for r=r_i+m_i-e.

As a consequence of the above, the scalar product (23) can be rewritten in a slightly more simplified form:

áf,gń_G=

ć
č

f₀

g₀

D
ĺ
r,s=1

m_rsf_r

g_s

ö
ř

(30)

The recurrence matrix

First, let us consider the (D+1)×(D+1) matrices B_i, 0 Ł i Ł D, whose entries are the intersection numbers of G; that is, (B_i)_jk=(p_ij^k). It is known that the character algebra, generated by the matrices B₀,B₁,Ľ,B_D, is isomorphic to the adjacency algebra A(G) (this is a generalization of a result from [4]). Since such an isomorphism assigns the matrix B:=B₁ to the matrix A =A₁, it turns out that B_k=p_k(B), 0 Ł k Ł D, and, consequently, it is enough to compute B₁, called the intersection or recurrence matrix. In particular, A and B have the same minimum polynomial and, consequently, the same distinct eigenvalues. As we have already seen, the entries of B =(p_1j^k) give the following recurrence satisfied by the distance polynomials

xp_j=

D
ĺ
k=0

p_1j^k p_k (0 Ł j Ł D)

(31)

where p₀=1 and p₁=x. (Remember that polynomial equalities must be understood in the quotient ring \mathbbC[x]/Á.) Since the entries of B correspond to the cardinalities p_1j^k=|G₁⁺(u)ÇG^-_j(v)|, provided that dist (u,v)=k, and G is D-regular, we infer that ĺ_j=0^D p_1j^k=D, for any k=0,1,...,D; that is, j is a left eigenvector of B with eigenvalue D. In particular, the last row of B is uniquely determined for the other D. In matrix form, the D+1 equations in (31) correspond to

Bp(x)=xp(x)

(32)

where p(x):=(p₀(x),p₁(x),Ľ,p_D(x))^T. Note that, for a given value of x and starting from p₀(x)=1 and p₁(x)=x, the j-th equation, 2 Ł j Ł D-1, allows us to compute the value of p_j+1(x) from those of p_k(x), k=0,1,Ľ,j, through the formula

j-1
ĺ
k=0

p_1j^k p_k(x) + (p_1j^j-x)p_j(x)+p_1j^j+1p_j+1(x)=0 ;

(33)

whereas the last equation (j=D), which we write in the form

p_D+1(x):=(x-p_1D^D)p_D(x)-

D-1
ĺ
k=0

p_1D^k p_k(x)=0 ,

(34)

yields a condition for p(l) being a (right) eigenvector of B with eigenvalue l, namely that p_D+1(l)=0. (Notice again that p_D+1=0 must be understood in the quotient ring \mathbbC[x]/Á.) From this, we infer that the characteristic polynomial of B, which coincides with the minimum polynomial of B as both have the degree D+1 (and the later divides the former), is

y_B (x):=

det

(xI-B) =

a_D^D

p_D+1(x).

(35)

Let l_i be an eigenvalue of B with eigenvector v_i:=p(l_i), and assume that its multiplicity, as a zero of y_B, is m_i (1 Ł m_i Ł m(l_i)). Then we can repeatedly take the derivative of (32) and evaluate at x=l_i to obtain

Bp(l_i)

l_ip(l_i),

Bp˘(l_i)

p(l_i) + l_ip˘(l_i),

Bp" (l_i)

2p˘(l_i) + l_ip"(l_i),

Bp^(m_i-1)(l_i)

(m_i-1)p^(m_i-2)(l_i) +l_ip^(m_i-1)(l_i).

Then, dividing the k-th equation by (k-1)!, 1 Ł k Ł m_i, and writing all the resulting equalities in matrix form we get

B¶_i = ¶_i J_i (0 Ł i Ł d),

(36)

where

¶_i:=

ć
ç
č

p(l_i)

p˘(l_i)

p"(l_i)

p^(m_i-1)(l_i)

(m_i-1)!

ö
÷
ř

is the matrix formed by the m_i columns of ¶ with indices r_i, r_i+1,Ľ, r_i+m_i-1 (see the previous subsection) and J_i is the Jordan block of size m_i for the eigenvalue l_i:

J_i:=

ć
ç
ç
ç
č

l_i

^··_·

l_i

ö
÷
÷
÷
ř

Consequently, we have proved the following result:

Proposition 2 Let G be a weakly distance-regular digraph of degree D, diameter D, and distance-polynomials {p_k}_k=0^D. Let A and B =(p_1j^k) be, respectively, its adjacency and intersection matrices. Then, the following statements hold:

$(i)$ The minimum polynomials of A and B coincide with the characteristic polynomial of B which is

y_B = 1
a_D^D
p_D+1 = 1
a_D^D
(x-D) D
ĺ
k=0
p_k,

where a_D^D is the leading coefficient of p_D and p_D+1 is the polynomial defined in (34).
$(ii)$ If l_i is an eigenvalue of B, then v_i=(p₀(l_i),p₁(l_i),...,p_D(l_i))^T is a (right) eigenvector of B corresponding to l_i.
$(iii)$ If B has spectrum sp B ={l₀,l₁^m₁,Ľ,l_d^m_d} then it has Jordan normal form J_B with blocks J₀,J₁,Ľ,J_d and transformation matrix ¶:

¶^-1B¶ = J_B .

Notice that the first component of each of the eigenvectors v_i is 1 as p₀=1. In this case we say that the eigenvector is standard . Furthermore, if all the eigenvalues of B are simple then {v_i}_i=0^D is a basis for \mathbbC^D+1 (equivalently, B diagonalizes on \mathbbC). The following result shows that, in this case, B has also a standard left eigenvector for every l_i, denoted by u_i (as a column vector), and this allows us to compute the multiplicity of l_i as an eigenvalue of G.

Proposition 3 Let G be a weakly distance-regular digraph with order N, diameter D, and intersection matrix B. If each eigenvalue l_i of B is simple, then l_i has standard left and right eigenvectors, u_i^T and v_i, and the multiplicity of l_i as an eigenvalue of G is

m(l_i)= N
u_i^T v_i
(0 Ł i Ł d).
(37)

Proof. Let p₀=1,p₁,Ľ,p_D be the distance polynomials of G. Since all the zeros of m_G are simple, then D=d and the (standard) right eigenvectors v_j, 0 Ł j Ł d, are the columns of the matrix ¶_ev=(p_i(l_j)). Furthermore, since {v_j}_j=0^d is a basis of \mathbbC^d+1, ¶_ev is invertible, and the rows of ¶_ev^-1 are left eigenvectors for B. So, from any set {u_i}_i=0^d of such eigenvectors, we can write ¶_ev^-1=D^-1U , where D:= diag (u₀^Tv₀,u₁^Tv₁Ľ,u_d^Tv_d) and U is the matrix with rows u₀^T,u₁^T,Ľ,u_d^T. Thus, by Proposition 3.1,

m(l_i)=N (D^-1U)_i0 = N

u_i0

u_i^Tv_i

(0 Ł i Ł d).

This proves both statements since, as m(l_i) ą 0, it must be that u_i0 ą 0 and hence we can chose every u_i, 0 Ł i Ł d, in such a way that u_i0=1. (As a by-product, notice also that u_i^Tv_i must be a real number.) ^[¯]

Here it is worth mentioning the similarity between (37) and the known formula to compute the multiplicities of a distance-regular graph G. Thus, since the corresponding symmetric digraph G =G^* (obtained by replacing every edge of G by a digon) is distance-regular, the above can be seen as an extension of such a formula to the (more general) directed case. In fact, if G is a distance-regular digraph we have, from the orthogonality of the distance polynomials and the simple form of the scalar product (18), that u_i=([ 1/(n₀)][`(p₀(l_i))],[ 1/(n₁)][`(p₁(l_i))],Ľ, [ 1/(n_d)][`(p_d(l_i))]), where n_j=n_j(u)=p_j(D), 0 Ł j Ł d; and the way of computing (37) from such polynomials is the same as for distance-regular graphs (see e.g. Bannai and Ito [2] or Biggs [4]).

4 Some constructions

In this last section we give several constructions and examples of weakly distance-regular digraphs. (For the case of diameter two, we refer the reader to the known constructions of directed strongly regular graphs [5].) For instance, it is shown that every line digraph of a (standard) distance-regular digraph is weakly distance-regular. Moreover two families of digraphs, well-known in the context of network theory, are shown to be weakly-distance regular and so they are analyzed in the light of the present theory.

Of course, (trivial) examples of weakly distance-regular digraphs are the known distance-regular digraphs but, for degree D > 1, they can only exist for diameter D and girth g satisfying D Ł g Ł 8, if g > 2; see [10]. Other easy examples are obtained from the distance-regular (undirected) graphs, which can be seen as distance-regular digraphs with girth two. Indeed, given a distance-regular graph G, its symmetric digraph G = G^* is clearly a weakly distance-regular digraph.

Let us now see that, through the line digraph technique [16], every distance-regular digraph gives rise to a weakly distance-regular digraph. For a given digraph G, its line digraph LG has vertices representing the arcs of G, and vertex uv is adjacent to vertex wz when the corresponding arcs are adjacent in G; that is, when v=w.

Proposition 1 Let G be a distance-regular digraph different from a cycle (D > 1), with girth g and diameter D. Then its line digraph LG is a weakly distance-regular digraph. Moreover, if 1,x,p₂,...,p_D are the distance polynomials of G, then the distance polynomials of LG are

1,x,xp₁,...,xp_g-2,xp_g-1-1,xp_g,Ľ, xp_D.

Proof. Let A and [(A)\tilde] be the adjacency matrices of G and LG, respectively. Then, the number of walks of length l+1 from vertices uv ą wz of LG, such that dist (uv,wz)=k+1, 0 Ł k Ł D, is

(l+1)
uv,wz

=a_v,w^(l)=a_k^l

since dist (v,w)=k; whereas in the case uv=wz (that is, dist (uv,wz)=0) we have

(l+1)
uv,uv

=a_v,u^(l)=a_g-1^l

as dist (u,v)=1 implies dist (v,u)=g-1. Thus the number of such walks only depend on the distance between vertices, and LG is weakly distance-regular.

Moreover, if p_k is the k-th distance polynomial of G, 0 Ł k Ł D, then

(

p_k(

))_uv,wz=(p_k(A))_vw=(A_k)_vw.

Therefore, taking into account that ([(A)\tilde]_k+1)_uv,wz=(A_k)_vw, if uv ą wz, and

(

k+1

)_uv,uv=0=

ě
í
î

(A_k)_vu

k ą g-1

(A_k)_vu -1

k = g-1,

we conclude that the (k+1)-th distance polynomial of LG is xp_k, if k ą g-1, and xp_g-1-1, if k=g-1. ^[¯]

In fact, note that the above result still holds under some slightly less restricted condition on G. For instance, it suffices to require G to be weakly distance-regular, and with every arc (u,v) contained in a cycle of smallest length g (for then dist (v,u)=g-1). For example, this is the case when G =G^*, G being a distance-regular graph, as mentioned above. More generally, we can consider a weakly distance-regular digraph G with every arc a contained in the same number of closed walks of length l ł 0. (This is equivalent to require that LG must be a `walk regular digraph', a concept defined by Godsil [17] in the undirected case). As we will see, an example of digraphs satisfying these properties are the so-called butterfly networks, which are the topic of the next subsection.

The butterfly networks

Butterfly networks have been extensively studied in the literature because of their multiple applications in computer architecture (see e.g. [3,13,18]). In particular, the wrapped butterfly digraph G =B_D(n), of degree D and dimension n, has vertices labeled by the pairs (l,x), where l Î \mathbbZ_n and x Î \mathbb Z_Dⁿ; and vertex (l, x₀x₁...x_n-1) is adjacent to the vertices ( l+1, x₀ ...x_l-1y_l x_l+1... x_n-1) for any y_l Î \mathbb Z_D. Thus G is a regular digraph with degree D, order N=nDⁿ, girth g=n, and diameter D=2n-1.

Proposition 2 The wrapped butterfly digraph G =B_D(n) is a weakly distance-regular digraph with distance polynomials

p₀ = 1,    p₁=x,    Ľ,   p_n-1=x^n-1,    p_n = xⁿ-1, p_n+1= 1
D
xⁿ⁺¹-x,   Ľ,    p_2n-1= 1
D^n-1
x^2n-1-x^n-1.

Furthermore, the eigenvalues of B_D(n) are

l_i=Dwⁱ    (0 Ł i Ł n-1)      and       l_n=0,

where w is any primitive n-th root of unity, say, w:=e^j[(2p)/n], with respective multiplicities

m(l_i)=1    (0 Ł i Ł n-1)      and       m(l_n)=N-n.

Proof.   The invariance of the number of walks, implying the weak distance-regularity, and the expressions for the distance polynomials follow immediately from the following well-known properties of B_D(n): (i) The lengths of all walks from vertex (l,x) to vertex (l˘,y) are congruent to l˘-l modulo n. (ii) For 0 Ł k Ł n, the number of vertices at distance k from a given vertex (l,x) is the maximum possible for a D-regular graph with girth g=n, that is, D^k if 0 Ł k Ł n-1 and Dⁿ-1 when k=n. This means that the (shortest) path from (l,x) to each of these vertices is unique. (iii) For n+1 Ł k Ł 2n-1, the number of walks of length k from (l,x) to every vertex of the form (l+k,y) (including those previously reached) is D^k-n. (To see this, use induction on k.)

Now, from the distance polynomials and Proposition 3.2(i), we know that, apart from l₀=D, the distinct eigenvalues of G are the zeros of the polynomial

S:=

D
ĺ
k=0

p_k=xⁿ

ć
č

)²+Ľ+(

)^n-1

ö
ř

;

that is, l_i=Dwⁱ, 1 Ł i Ł n-1, and l_n=0. Thus,

¶_ev=

ć
ç
ç
ç
ç
ç
ç
č

Dw^n-1

D²

D²w²

D²w^(n-1)2

^··_·

Dⁿ-1

Dⁿwⁿ-1

Dⁿw^(n-1)n-1

-1

ö
÷
÷
÷
÷
÷
÷
ř

has an inverse matrix with first column [ 1/N](1,1,Ľ, 1,N-n)^T since n + (N-n) = N, D^kĺ_i=0^n-1w^ik = 0 for any 1 Ł k Ł n-1 and, using that N=nDⁿ, ĺ_i=0^n-1(Dⁿwⁱⁿ-1)+(N-n)(-1) = n(Dⁿ-1)-N+n = 0. (Of course, this corresponds to verifying the equations (20).) Consequently, the multiplicities are as claimed. ^[¯]

If we allow the presence of multiple arcs, we can reach to the same result in the following way. Let C_n^D be the directed cycle on n vertices and D parallel arcs between any adjacent vertices. So, C_n^D is a weakly distance-regular digraph with girth g=n, diameter D=n-1, and distance polynomials p_k=[ 1/(D^k)]x^k, 0 Ł k Ł n-1. Moreover, for any given 1 Ł l Ł n, every walk of length l is contained in a (smallest) cycle of length n. Thus, Proposition 4.1 can be repeatedly applied to prove that the iterated line digraph LⁿC_n^D is a weakly distance-regular digraph with the same parameters as B_D(n). Then, as both digraphs can be shown to be isomorphic, we get again Proposition 4.2. (To see more details about the relationship between the spectra of a digraph and its line digraph, see [24,22].)

The cycle prefix digraphs

The cycle prefix digraphs were introduced by Faber and Moore as a Cayley coset digraphs, although to study some of their properties it is more useful to consider them as digraphs on alphabets (see [14,7]). The cycle prefix digraph G =G_D(D) has vertices of the form x₁x₂Ľx_D where the x_i˘s are distinct elements from the set {1,2,Ľ,D+1}, and vertex x₁x₂Ľx_D is adjacent to the vertices x₂Ľx_Dx_D+1 and x₁x₂Ľx_k-1x_k+1Ľx_Dx_k, 2 Ł k Ł D-1. Thus, G is a D-regular digraph, with order N=(D+1)_D:=[((D+1)!)/((D+1-D)!)] and diameter D Ł D. Moreover, in [23,8] the first and last authors showed that the eigenvalues of G are D,D-2,D-1,Ľ,0,-1. In fact they obtained this result by proving the existence of the distance polynomials, so that the cycle prefix digraph is an example of weakly distance-regular digraph. To show that this is a `genuine' example, and G_D(D) is not distance-regular, notice that its girth is g=2 since the digraph has digons. Let us consider the vertices u=x₁x₂ ... x_D and v=x₂... x_Dx₁. Clearly dist (u,v)=1 but dist (v,u) > 1 if D > 1. Hence, the digraph is not stable. (The above can also be proved directly from the definition of strongly distance-regular digraph given in [9].)

Given an integer x ł 2, let us denote by P_x the set of (ordered) t-tuples (x₁,x₂,Ľ,x_t), which are a partition of x, x₁+x₂+Ľ+x_t=x, with x_i ł 2 for any 1 Ł i Ł t. (Thus, 1 Ł t Ł ëx/2ű.) Now, let Y be the function defined on the nonnegative integers as

Y(0):=1, Y(1):=0, and Y(x):=

ĺ
(x₁,x₂,Ľ,x_t) Î P_x

t
Ő
i=1

(x_i-2)!

x_i

(x ł 2).

For example, Y(5)=[ 3!/5]+[ 0!/2][ 1!/3]+[ 1!/3][ 0!/2] = [ 23/15]. By looking at the possible values of the first term x₁, we get the following useful recurrence formula for computing Y:

Y(x+1)=

x-1
ĺ
y=0

(x-y-1)!

x-y+1

Y(y).

(38)

In the next result we also use the following notation. For any given integer k ł 1, let (x)_k denote the polynomial in x obtained as the product x(x-1)(x-2)Ľ(x-k+1) (note that this definition is consequent with the meaning of (D+1)_D).

Theorem 3 The cycle prefix digraph G =G_D(D) is a weakly distance-regular digraph with distance polynomials

p₀=1, p₁=x, p₂= (x+1)₃
x
, p₃ = (x+1)₄
x-1
, Ľ, p_D= (x+1)_D+1
x-D+2
.

Moreover, the eigenvalues of G are

l₀=D    and    l_i=D-i-1        (1 Ł i Ł D),

with respective multiplicities

m(l₀) = 1, m(l₁)= 1
(D-1)!
(D+1)_D+1
D-D+2
, m(l₂)= 1
(D-2)!
(D+1)_D
D-D+3
,
(39)

m(l_i) = 1
(D-i)!
i-1
ĺ
x=0,x ą i-2
Y(i-1-x) (D+1)_D+1-x
D-D+2+x
      (3 Ł i Ł D-1),
(40)

m(l_D) = (D+1)_D- D-1
ĺ
i=0
m(l_i).
(41)

Proof.   As already mentioned, the distance polynomials and the eigenvalues were given in [8]. Indeed, from such polynomials, the eigenvalues are l₀=D and the zeros of

D
ĺ
k=0

p_k=1+

D+1
ĺ
k=2

(x+1)_k

(x-k+3)

=(x+1)_D

(to prove the last equality, use induction on D), which gives the above values for l_i, 1 Ł i Ł D. Then, notice that p_D(l_i)=0 for any i=2,3,Ľ,D; and, when 1 Ł k Ł D-1, p_D-k(l_i)=0 for any i=k,k+2,k+3,Ľ,D. Consequently, the matrix ¶_ev has the following quasi-triangular form

¶_ev=

ć
ç
ç
ç
ç
ç
ç
ç
č

l₁

l_D-2

-1

p₂(D)

p₂(l₁)

p₂(l_D-1)

p₃(D)

p₃(l₁)

p₃(l_D-2)

p_D-1(D)

p_D-1(l₂)

p_D(D)

p_D(l₁)

ö
÷
÷
÷
÷
÷
÷
÷
ř

which, from (20), allows us to obtain the claimed multiplicities recursively from m(D)=1,

m(l₁)=-

p_D(D)

p_D(l₁)

, m(l₂)=-

p_D-1(D)

p_D-1(l₂)

and

m(l_i)=

-1

p_D-i+1(l_i)

i-1
ĺ
j=0

p_D-i+1(l_j)m(l_j) (3 Ł i Ł D-1)

by using (38) (we skip the cumbersome details). Finally, m(l_D) is obtained from the first equation expressing that all multiplicities add up to N=(D+1)_D. ^[¯]

A possible generalization

We end this section with a digression about a natural generalization of weak distance-regularity and its relation with some of our results. In the last section of Damerell's paper [9], entitled Related problems , the author introduce the notion of the so-called weakly distance-transitive digraph. According to him, a digraph G is weakly distance-transitive if G is connected and for any pairs of vertices, (u,v) and (w,z), such that

dist (u,v)= dist (w,z) and dist (v,u)= dist (z,w),

there exists an automorphism p Î Aut G such that p(u)=w and p(v)=z. (Damerell argues that this would be a definition closer to the corresponding concept for graphs). Inspired by this, we could consider an alternative (non-equivalent) definition of a weakly distance-regular digraph G as the digraph satisfying the following condition:

dist

Or, in terms of the adjacency matrix A of G,

Observe that condition (W*) is stronger than the property characterizing walk regular digraphs, but `weaker' that our condition characterizing weakly distance-regularity. Namely,

dist

In this context we have the following result (we omit the proof, as some of the equivalences have been already given):

Theorem 4 Let G =(V,E) be a digraph with adjacency matrix A and girth g. Then the following statements are equivalent

$(a)$ G is distance-regular.
$(b)$ G satisfies condition (W^*) and it is stable.
$(c)$ G satisfies condition (W) and, for any pair of vertices u,v Î V, we have dist (u,v)=1 Ű dist (v,u)=g-1 (or, equivalently, A^T=A_g-1).
$(d)$ G satisfies condition (W) and A is normal.

One of the referees pointed out that, recently, H. Suzuki and K. Wang [27] suggested that a `weakly distance-regular digraph' is a digraph with the following property: for vertices u and v such that dist (u,v)=k₁ and dist (v,u)=k₂, the number of vertices z satisfying dist (u,z)=i₁, dist (z,u)=i₂, dist (v,z)=j₁, and dist (z,v)=j₂ depend only on the values k₁,k₂,i₁,i₂,j₁,j₂. (This is equivalent to require that the Hadamard products A_i°A_j^T form an association scheme.) Weakly distance-transitive digraphs satisfy this property, but it is not clear wheter these digraphs are easily related with property (W^*).

Acknowledgment. The authors are indebted to the referees for helpful comments and suggestions which lead to numerous improvements of the manuscript.

References

[1]: E. Bannai, P. J. Cameron and J. Kahn, Nonexistence of certain distance-transitive digraphs, J. Combin. Theory Ser. B 31 (1981), 105-110.
[2]: E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings, Menlo Park, CA, 1984.
[3]: J.-C. Bermond, E. Darrot, O. Delmas, and S. Perennes, Hamilton circuits in the directed wrapped butterfly network, Discrete Appl. Math. 84 (1998), no. 1-3, 21-42.
[4]: N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974; second edition: 1993.
[5]: A. Brouwer, personal homepage: http://www.cwi.nl/~aeb/math/dsrg/dsrg.html
[6]: R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, Cambridge, 1991.
[7]: F. Comellas and M.A. Fiol, Vertex-symmetric digraphs with small diameter, Discrete Appl. Math. 58 (1995), no. 1, 1-12.
[8]: F. Comellas and M. Mitjana, The spectra of cycle prefix digraphs, SIAM J. Discrete Math. 16 (2003), no. 3, 418-421.
[9]: R.M. Damerell, Distance-transitive and distance-regular digraphs, J. Combin. Theory Ser. B 31 (1981), no. 1, 46-53.
[10]: D. A. Douglas and K. Nomura, The girth of a directed distance-regular graph, J. Combin. Theory Ser. B 58 (1993), no. 1, 34-39.
[11]: Art M. Duval, A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A 47 (1988), no. 1, 71-100.
[12]: H. Enomoto and R.A. Mena, Distance-regular digraphs of girth 4, J. Combin. Theory Ser. B 43 (1987), no. 3, 293-302.
[13]: M. Espona and O. Serra, Cayley digraphs based on the de Bruijn networks, SIAM J. Discrete Math. 11 (1998), no. 2, 305-317.
[14]: V. Faber, J. W. Moore, and W. Y. C. Chen, Cycle prefix digraphs for symmetric interconnection networks, Networks 23 (1993), 641-649.
[15]: M. A. Fiol, Algebraic characterizations of distance-regular graphs, Discrete Math. 246 (2002), no. 1-3, 111-129.
[16]: M. A. Fiol, J. L. A. Yebra, and I. Alegre, Line digraphs iterations and the (d,k) digraph problem, IEEE Trans. Comput. C-32 (1984), 400-403.
[17]: C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
[18]: R. Klasing, R. Lüling, and B. Monien, Compressing cube-connected cycles and butterfly networks, Networks 32 (1998), no. 1, 47-65.
[19]: C. W. H. Lam, Distance-transitive digraphs, Discrete Math. 29 (1980), no. 3, 265-274.
[20]: P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic Press, Orlando, FL; second edition: 1985.
[21]: R. A. Liebler and R. A. Mena, Certain distance-regular digraphs and related rings of characteristic 4, J. Combin. Theory Ser. A 47 (1988), no. 1, 111-123.
[22]: X. Marcote, C. Balbuena, and I. Pelayo, The relationship between the Jordan normal forms of a digraph and its line digraph, submitted.
[23]: M. Mitjana, Propagació d'informació en grafs i digrafs que modelen xarxes d'interconnexió simètriques (Catalan), Ph.D. Thesis, Universitat Politècnica de Catalunya, 1999.
[24]: J. C. Montserrat, Propiedades matriciales de los grafos dirigidos (Spanish), Master Thesis, Universitat Politècnica de Catalunya, 1986.
[25]: P. Rowlinson, Linear algebra, in: Graph Connections (ed. L.W. Beineke and R.J. Wilson), Oxford Lecture Ser. Math. Appl., Vol. 5, 86-99, Oxford Univ. Press, New York, 1997.
[26]: T. Takahashi, Distance-regular digraphs of girth 6, Memoirs of the Faculty of Science, Kyushu University, Ser. A 45 (1991), no. 2, 155-166.
[27]: K. Wang and H. Suzuki, Weakly distance-regular digraphs, Discrete Math. 264 (2003), no. 1-3, 225-263.

Footnotes:

¹Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Jordi Girona 1-3, Mòdul C3, Campus Nord, 08034 Barcelona, Spain.

²Departament de Matemàtica, Universitat de Lleida, Jaume II 69, 25005 Lleida, Spain.

³Departament de Matemàtica Aplicada I, Universitat Politècnica de Catalunya, Gregorio Marañon 44, 08028 Barcelona, Spain.

⁴If a weakly distance-regular digraph G contains a loop, then each vertex has the same number of loops. Moreover, if G contains a multiple edge, then all edges of G are multiple (with equal "multiplicity"). Hence, the deletion of all such repetitions and loops provides another weakly distance-regular digraph.

File translated from T_EX by T_TH, version 3.40.
On 26 Jun 2003, 19:19.

Weakly Distance-Regular Digraphs

F. Comellas1, M. A. Fiol, J. Gimbert2, and M. Mitjana3

September 9, 2002

Abstract

1 Introduction

Distance-transitivity and distance-regularity

2 Weak distance-regularity

3 The spectrum and the condensed matrices

The multiplicities

The multiplicity matrix

The recurrence matrix

4 Some constructions

The butterfly networks

The cycle prefix digraphs

A possible generalization

References

Footnotes:

F. Comellas¹, M. A. Fiol, J. Gimbert², and M. Mitjana³