A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs

A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs

DISCRETE APPLIED MATHEMATICS ELSWIER Discrete Applied Mathematics 77 (1996) 1I8 99- A new digraphs composition with applications to de Bruijn an...

1MB Sizes 0 Downloads 3 Views

DISCRETE APPLIED MATHEMATICS ELSWIER

Discrete Applied

Mathematics

77 (1996)

1I8

99-

A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs* Dominique LRI,

CA 410 CNRS,

Barth *, Marie-Claude hdr 490. Uniwrsit~~ & Paris-Sud,

Received

17 November

Heydemann 91405 Olscr~~ Ce&s.

1995; revised 25 September

Frunw

1996

Abstract In this paper.

we introduce

a new

operation

on digraphs

that we apply

to different

cases;

we

that this new operation commutes with the operation of taking the line digraph. In particular, we give a simple construction of the Kautz digraph of diameter n from two de Bruijn digraphs of diameter n - I and n. We also study k-factors in the composed digraph with application to the counting of l-factors of de Bruijn and Kautz digraphs. give

new

Kqwords:

results

about

de Bruijn

digraphs

and

generalized

de Bruijn

digraphs.

We prove

Digraph; De Bruijn digraph; Kautz digraph; k-factor

1. Introduction The construction

For example, interconnection

and the study

of digraphs

in relation

to applications

to networks

have been especially studied. Kautz and de Bruijn digraphs possess good properties as underlying networks for designing parallel architectures (see, e.g., [5,7, 19,201).

has well-established

literature.

Some

families

of digraphs

These digraphs are also good models for designing large packet radio networks [4]. The usual definitions of Kautz and de Bruijn digraphs are based on alphabets, or on iterated line digraphs constructions (see Section 2.3). Some other ways of defining the de Bruijn digraph have been proposed. In [9], a construction of a large binary de Bruijn digraphs from partial subdigraphs of lower dimension is given; this is used to make an efficient Viterbi decoder. H. Fredricksen also proposed new descriptions based on special circuits of the binary de Bruijn digraph [14]. We give here a new recursive construction of de Bruijn and Kautz digraphs. Our study has been mainly motivated by a problem of J.-L. Fouquet. The problem was to relate the Kautz digraph K(d,D) and de Bruijn digraphs B(d,D- 1) and B(d, D)

This work was supported by the “Optration * Corresponding author. E-mail: [email protected] 0166-218X/96/$17.00 0 PIISOl66-218X(96)00130-8

1996 Published

RUMEUR”

by Elsevier Science

of the French GDRiPRC

B.V. All rights reserved

PRS C’

100

D. Barth,

(see the definition

M.-C.

Heydemannl

Discrete

Applied

Mathematics

99-I 18

in Section 2) in order to deduce results on factorization

from similar results on the other one (see Section 5). To answer Fouquet’s question we give a construction starting

77 (1996)

with the de Bruijn

digraphs

can be applied to other digraphs.

of the Kautz digraph K(d,D)

B(d, D - 1) and B(d,D).

Thus, we introduce

of one family

But this construction

a new simple operation

on di-

graphs which, given a digraph 9, construct a new digraph $(9), by exchanging outneighbours of some chosen pairs of vertices of 9 {u, 4(u)}. In the case where 9 is the union of a digraph and its line digraph, we prove that this new construction commutes with the operation of taking the line digraph and deduce as a corollary the announced construction of K(d,D) from B(d,D - 1) and B(d,D). By means of this construction, we obtain recursive constructions of some de Bruijn and generalized de Bruijn digraphs. We also study k-factors in $(%‘J) from those of 9. We determine the number of lfactors of de Bruijn digraphs and deduce the number of l-factors of Kautz digraphs. We relate this to the routing of a particular set of permutations in this digraphs. This paper is organized as follows. The basic terminology and notation is introduced in Section 2. We define the new operation on digraphs in Section 3. We apply it to de Bruijn digraphs in Section 4. In Section 5, we consider the particular case of composition of a digraph and its line digraph and we apply our results to de Bruijn digraphs. The case of generalized de Bruijn digraphs is studied in Section 6. An application of the constructions to k-factors is given in Section 7.

2. Definition,

notation and preliminary

results

2.1. Digraphs Definition not given here can be found in [3]. In this paper, we deal only with directed graphs (digraphs). set Y = V(G) and arc set A = A(G) is denoted

A digraph G with vertex

G = (V,A). An arc from vertex u to

vertex u is denoted (u, v) (or possibly [u, U] if it is more convenient). If (u, v) is an arc, then u is said to be an in-neighbour of v and symmetrically v is an out-neighbour of u. The set of in-neighbours of u is T;(u) = {v E V(G) : (v, u) E A(G)} and is called the in-degree of u. Similarly, the set of vertices of out&(u) = lC&)l neighbours of u is T:(u) = {v E V(G) : (u,v) E A(G)) and 6:(u) = ITA(u)l is the out-degree of u. For any vertex u of G, do(u) = min(P(u), 6-(u)). We denote 6(G) the minimum taken over all the vertices u of G of do(u). Digraph G is d-regular if Vu E G; 6;(u) = 6;(u) = d. A directed path (dipath) from vertex u to vertex v in digraph G is a sequence of adjacent arcs, where u is the initial extremity of the first arc and v is the final extremity of the last arc. The distance from u to v in V(G), distc(u,v), is the length of a shortest dipath from u to v. The diameter of G is D(G) = max,,(distc(u,v)). The union of digraphs G and H, denoted G U H, is the digraph with vertex set V(G UH) = V(G)U V(H) and edge set A(GUH) =,4(G) UA(H). The weak product

D. Barth, M.-C. Hevdemann I Discrete Applied Mathematics 77 (I 996) 99- 1 IK

G and H, denoted

of digraphs V(G)

x V(H)

%4?

G x H, is the digraph

:x E V(G),

Y’ E r,+(Y)).

V(L(G))

= A(G),

y E F:(x),

with vertex set V(G x H) =

and edge set A(G x H) = {[(x,y),(x’,y’)]

We denote by L(G) the

of G. The vertices

line digvaph

and the arcs of L(G)

101

of L( G)

are all the couples

1: E V(H),

x’ t

are the arcs of G. i.e. x E V(G),

[(x,y),(v,z)].

z E T:(y).

be often denoted

For sake of simplicity, arcs of L(G), like [(x,JJ), (J;z)], will as dipaths of length 2 in G, i.e. (x, 2;~). We also denote inductively for all k > 1.

Lk(G) = L(L”-‘(G)), 2.2. Muppings

and isomorphisms

If ,f : V --i V’ is a mapping from set V to set V’, we denote hf the set of vertices {U E V’ : 3u E V, f(u)= u}.A mapping $ : V(G) 4 V(G) is said to be involufire if for any vertex u E V(G), 4(&u)) = U. Such a mapping is bijective. In this article, we will often prove that two digraphs G and H are isomorphic. For this, we will construct a mapping h : V(G) + V(H), which is bijective, arcpreserving, i.e. for any arc (u,u’) of G, (h(u),h(u’)) is an arc of H, and such that the inverse mapping h-’ is also arc-preserving. Such a mapping is an isomorphism from G to H. In the following we will use in several proofs the following property without recalling it. Lemma 1. Let G und H be ttro digruphs, h : V(G)

+

V(H),

luhich is bijectiae

particular

if G und H are both regulur

Mith IV(G)1

=

and arc-preserving. qf the same degree),

lV(H)I,

and u mupping

Jf IA(G)1 =

IA(H)1

(in

then h is un isomorphism

and G and H ure isomorphic.

2.3. de Bruijn and Kuutz digruphs Let i& = (0, l,...,d

- I} denote an alphabet of d letters and Z; = {XIX? . ..x._Is,

:

x, E Zd} the set of all d-ary words on & of length n. A word xx.. .x E Z:, x E h,,. is denoted x”. For x E Zz, X = 1 -x,

and for xl . ..x., t Zz, m=q...X,.

Let B(d,D) and K(d,D) denote de Bruijn and Kautz digraphs, degree d > I and diameter D > 0 [S, 171. Then V(B(d,D))

with

= Z:,

A(B(d, D)) = For example,

respectively,

{(X,X2...xD,x2...

B(3,2)

is depicted

V(K(d,D))

= {XIX~...XD

A(K(d,D))

={(x,x~...x~,x~...

xpco+l):Vi,I


:x,t&}.

in Fig. 1

: Vi :x, E &+l,Vj,l xIjxD+l):



- 1 :x, #x,+1}.

Ifi : xi E Zd+l;Yi,

1
x, # x;_l}.

102

D. Barth, M.-C.

HeydemannlDiscrete Applied Mathematics

77 (1996)

99-118

01

10 21 0 20

12 @

WV) Fig. 1. Digraphs

K(U) B(3,2)

and K(2,2)

For example, K(2,2) is also depicted in Fig. 1. Let K; denote the complete digraph with vertex set Zd and let Kd+ denote K$ augmented with a loop at each vertex. Kj = K(d, 1) and Kd+ = B(d, 1). It was shown in [l l] that for d 3 2 and D 3 2, the de Bruijn by line digraph iteration: B(d,D)

= L(B(d,D

K(d,D)

= L(K(d,D

and Kautz digraphs

can be obtained

- 1)) = L=‘(K,+), - 1)) = LD-‘(K;+,).

2.4. Generalized de Bruijn and Kautz digraphs The generalized de Bruijn digraph and Kautz digraph (or Imase and Itoh digraph), denoted by GB(N,d) and IZ(N,d), respectively, are defined for all values of N and d, with d 2 2 [lo, 151. The generalized de Bruijn digraph GB(N,d) is defined by - V(GB(N,d)) = &, _ a couple of vertices (x, u) is an arc of GB(N,d) iffy = dx+r [N] with 0 < Y < d- 1. GB(N,d) is a d-regular digraph. If N = d”, then GB(N,d) is isomorphic to B(d,n). The generalized Kautz digraph II(N,d) is defined by ~ V(IZ(N,d)) = &,I, _ a couple of vertices (x, y) is an arc of II(N, d) iff y E -dx - Y [N] with 1 < Y < d. ZI(N,d) is also a d-regular digraph and if N = d” + d”-‘, then IZ(N,d) is isomorphic to K(d,n). In the following we will use the fact that, as for non-generalized digraphs, for any positive integer p, GB(dPN,d) and ZZ(dpN,d) can be obtained by line digraph iteration from GB(N,d) and IZ(N,d), respectively. This is the consequence of the following propositions.

D. Barth, M.-C. Heydemann I Discrete

Proposition

1. (Fiol et al. [ll]).

Applied Mathematics 77 (1996)

99-118

For all integers d > 1 and N > 0, L(GB(N,d))

103

=

GB(dN, d). An isomorphism

of L(GB(N,d))

is given by the mapping

and GB(dN, d), we will use in a proof of Section 5,

@ from A(GB(N,d))

= V(L(GB(N,d)))

fined by @(x,v> = dx+r if (x, v) E A(GB(N,d)) (notice that 0 d dx + r < dN - 1). Proposition

2. (Homobono

with .V = dx+r

into V(GB(dN,d))

de-

[N] and 0 < r < d- I

[16]). For all integers d > 1 and N > 0, L(II(N,d))

=

Il(dN, d).

3. The composition

operation

Given a digraph 9 and an involutive mapping C#I: V(3) + V(Y) ( 4(&x)) = x, for any vertex x, of 9), we define a new digraph S4(9) obtained from 9 by exchanging for any vertex x the out-neighbours of x and 4(x). More precisely, - V($(Y)) = V(9), - E&CYJ(x) = Ts($(x)) This is equivalent to

for any vertex x of $9.

~ A(&(~)) = {(X,Y) : x E V(W>Y E ~~Mx>>~. Since 4 is bijective and I#-’ = 4, equivalently, A&I(9))

=

{($(X)>Y) : Y fz V(%x

E l-&J)).

Thus, we remark, Remark 1. For any vertex x of 9, G&a,(x) This directly

implies the following

= S,(x),

and b;&IC9j(x) = 6$($(x)).

lemma.

Lemma 2. If9 is a d-regular digraph, then for any incolutioe mapping C,!I : V(9) V(Y), the digruph S&(3) is also d-regular. Notice

that if 4 is the identity,

then S$(%)

=

9. Furthermore,

--f

by definition,

S&$$(Y)) = 9. In the following we will mainly apply this construction to the case where 29 is a union of digraphs and [email protected](Y) is obtained by exchanging out-neighbours of pairs of vertices {x, C/I(X)} w h ere x and C&X) belong to different digraphs if 4(x) # x. The first part of Section 4 contains an example of graph L+(Y) where 9 is the union of several de Bruijn digraphs. But most of the time, the digraph $9 will be the union of only two digraphs G and H, i.e. 9 = G U H, and C#Iis an involutive mapping, 4: V(GuH) + V(G U H), such that ~ for any vertex x of G, either 4(x) = x or 4(x) E V(H), - for any vertex x of H, either 4(x) = x or 4(x) E V(G).

104

D. Barth,

M.-C.

HeydemannlDiscrete

In such a case the restriction

G C$ H to denote $,(G

notation

Thus, G @e H denotes the composition . l

77 (1996)

99-118

of 4 to V(G), denoted by $, is an injective mapping such that $(x) = x if I/(X) E V(G). Thus, we introduce

from V(G) to V(G) U V(H) the particular

Applied Mathematics

U

H) in this case.

of two digraphs

G and H such that

V(G Bti H) = V(G) u V(H), A(G @$ H) is the set of arcs defined for all u E I’(G) and v E V(H) by - (u,~‘),

with U’ E T:(U),

if $(u) = U, if $(u) E V(H), if v E Zm$,

- (u,u’), with ~1’E ri(Ic/(u)), - (u,u’), with U’ E T:(I,~‘(v)),

- (v, v’), with v’ E T;(v), if u @ Im $. An example of construction of G @‘II,H is given in Fig. 2. Notice that the definitions of $ and 4 are equivalent since, conversely, given an injective mapping $ from V(G) into V(G)U V(H) such that I/(X) = x if I/(X) E V(G), we can define 4 : V(G) U V(H) - 4(u) = $(u), for u E V(G), - 4(v) = $-l(v), if v E V(H) - 4(v) = v otherwise.

+

V(G) U V(H) by

and v E Zm$,

It is evident that 4(4(x)) =x for any vertex x of I’(G) U V(H). For sake of commodity, I’,,(G) will denote the set of vertices {U E V(G) : $(u) E JW)} = {u E V(G) : t&u) # ~1, and V$(H) the set Zm$ n V(H) = {v E V(H) : 3u E V(G), G(u) = u}. Mapping $ is a bijection from [email protected](G) onto [email protected](H). Notice that under the operation @i , graphs G and H play a symmetric role since G c$ H = S+(G u H) = $(H

u G) = H$‘G,

with $‘(y) = t+-‘(y) if y E V#(H), and $‘(y) = y if y E V(H) - V$(H). Before applying our composition to de Bruijn digraphs, we give some simple examples and properties

of digraphs

G Q, H.

Lemma 3. If G and H nre two isomorphic digruphs and $ is an isomorphism from G

to H, then [email protected]$H

is isomorphic to the weak product of G by the complete digraph

K2*. Proof. The vertex set of the weak product G x K; is {(u, 0) : u E V(G)} U {(u, 1) : u E V(G)} and its arc set is {[(u,O),(v, l)] : v E r:(u)} U {[(u, l),(v,O)] : v E r,‘(u)}. We define a mapping h from V([email protected]) to V(G x K,*) by h(u) = (u,O) for u E V(G)

d

G:

G': H:

or---y’

Fig. 2. Construction

of G’ = G @$ H for ti defined by $(u) = c, $(u’) = u’

D Barth, M.-C.

and h(v) = (~/~‘(v),l) isomorphism. 0

Heydernann I Di.tcrric Applied

for L: E V(H).

We give an easy application

Muthernatics

77 (1996 j 99- II8

We leave the reader to verify

105

that h is an

of Lemma 3. Let us denote C, the oriented

cycle on II

vertices. Example 1. In the case G = H = C, and $ is the identity, to C, u C,, if n is even and to C2n if n is odd.

G %I) H is isomorphic

This example shows that, if G and H are strongly connected, G & H is not necessarily strongly connected. In [2] we give sufficient conditions in order that G m:+,b H is strongly connected. The following simple lemma is in fact a corollary of Lemma 2. It will be used in the following sections. Lemma 4. If G and H are d-regubr digruphs, then ,for uny injective mupping $I : V(G) + V(G) u V(H), such that It/(x) = x if $(x) t V(G). the digruph G ‘Q, H is also d-regular. In the following,

we consider

only mappings

$ such that V$(G) # ti, and most of

the time such that V$(G) = V(G), so that $ can be considered from V(G) into V(H).

4. Application

to the construction

as a mapping

defined

of de Bruijn digraphs

As recalled in Section 2.3, de Bruijn digraphs can be obtained by line digraphs iteration. We propose here a simple recursive definition of B(d, n + 1) from B(d,n) using the operation define an involutive

S,. Let us denote by Bi(d,n), for i E Zd, a copy of B(d,n). We mapping 4 on UiEzc,V(B,(d,n)); let xl . . .x, be a vertex of B;(d, n)

&xl . . ..x,) = ix?. . .x, E V(B,,(d,n)) Proposition 3. For each integer n > 1, B(d,n + 1) is isomorphic is the union of d copies of B(d,n). Proof.

to &t,(9)

where 9

Denote simply [email protected](9) by S. The vertices of S are the vertices of the union of the

d copies of B(d,n) denoted Bi(d, n), for i E Zd. We denote by (i,xlxz .x,) the vertex XIX2 . ‘x, of the copy i, B,(d,n); hence by definition, for all u E i7zP’ and all ,j E &, 4(i,ju) = (j, iu). By construction, V(S) = {(i,xIx2.. ‘x,,) : i E &, ~1x2.. ‘x, E izi}, and A(S)= {[(i,iu),(i,ux)] : i E &,u E Zz-‘,x E &}U {[(i,ju),(j,ux)] : i E &, ,j # i, u E zy’, x E Z,}. By Lemma 2, S is d-regular. The two d-regular digraphs S and B(d, n + 1) have the same number of vertices and the same number of arcs.

106

D. Barth, M.-C.

We define ixlx2..

HeydemannIDiscrete

a mapping

f

from

‘x,, for any i E & and any

It is evident

that f

is bijective

V(S)

Applied

Mathematics

to V(B(d,n

77 (1996)

99-118

+ 1)) by f((i,~1~2

. ..x.))

=

since for u E Zz-’

and

~1x2 . . ‘x,, E zz. and is also arc-preserving

x 6 zd, _ arc [(i, iu),(i, ux)] of 5’ is sent by f onto (iiu,iux), _ arc [(i,ju),(j,ux)], with j # i, is sent by f onto (ijqjux). In each case the image is an arc of B(d, IZ+ 1). 0

Remark 2. (see definition, of Kd+.

In [2], we give a similar construction of the Butterfly digraph BF(d, n+ 1) for example, in [l] or [19]) from d copies of BF(d,n) and d”-’ copies

The construction of B(d, n + 1) from d copies of B(d, n) in the proof of Proposition 3 can also be described as follows. Take in each copy Bi(d, n) a spanning tree Ti, obtained by breadth-first search in Bi(d,n) starting with the root i”. Denote by T/ the digraph obtained from Ti by adding the loop (i”, i”) (see Fig. 3 for d = 2). The arcs of Ti are (i*u,iP-‘ux), with p > 0, u E ZsPp, x E &, and are unchanged in the construction. The leaves of C are all the vertices of Bi(d,n) whose first letter is different from i. So these leaves are the vertices of Bi(d,n) which are sent by 4 onto vertices of other copies Bj(d,n), j # i, i.e. vertices for which outgoing arcs are changed in the construction. Thus, in order to construct B(d, n + 1) from d copies of B(d, n), we only have to add outgoing arcs from the leaves of all the digraphs T:. In the particular case d = 2, we propose another mapping $ such that B(2, n + 1) = Bl(d,n) CQ Bz(d,n). Let Bl(2,n) and B~(2,n) denote two copies of B(2,n), and consider xi . . .x, E V(Bi(2, n)), with n > 1. We define a mapping $ from V(Bi(2, n))

Fig. 3. Digraphs T,‘, T[ in the case d = 2 and n = 4.

D. Barth, M.-C.

into V(B,(2,n))

so

U

He~demannlDisc~rrtr

Applied

Mathematics

77 (1996J

107

99-118

V(B2(2, n)) as follows: ~1x2 .__x, E V(Bz(2,n))

if xl = xi,

xi . .x, E V(B,(2,n))

else.

that

- V$//(B,(2,n)) = {Olu, lOU, U E z;-‘}, -

V+(B2(2,n))

Proposition

= {O%, 12U, 21E n;-‘}.

4. For each integer n > 1, B(2,n)

Q, B(2,n)

is isomorphic

to B(2,n+

1).

Proof. Let Bl(2,n) and &(2,n) denote two copies of B(2,n) and $ the mapping defined above. We consider the digraph 39$ = Bl(2, n) @II,&(2, n). We first define a mapping @ from V(a$) = Y(Bi(2,n)) U V(B2(2,n)) into Y(B(2,n + 1)) as follows. l If xl .x, E V(B1(2,n)), then @(xi . .x,) = ~1x1 .xn. l If x1 .x, E V(&(2,n)), then @(xl .xn) =x1x1 .x,. First of all, it is easy to see that CDis a bijection between I’(.%$) and V(B(2,n + 1)). Let (u, u’) be an arc in 39$ with u = xi . .x,,. (a) u E V(Bl(2,n)). We consider two cases. First, if XI = E, then by definition xix2. .xn), i.e. U’ = xl-x’, with x’ E (0, l}. Then, Q(u) = I-;32,n)( of $> u’ E x,2. Secondly, if XI = x2 then ..X,, and @(u’) = x1x1x3.. .x,2 = X1X*X3.. with x’ E (0, l}. Then Q(U) = ~1x1~2.. .x, and u’ E Ti,(2.,z,(z4), i.e. u’ = X2X3 . ..x.,x’, @(u’) = XIX?. . . x,x’ since XI =x2. In the two cases, (Q(u), @(u’)) E A(B(2,n + 1)). (b) II E V(&(2,n)). We also consider two cases: First, if XI = x2, then U’ E r,+,,,,n,(~-l(~)), i.e. U’ E fi,(2,n)(~iX2) and so u’ = -x,x’. Then, Q(U) = and @(u’) = ~2x2.. .x,x’ = x1x2.. .x,,x’. Secondly, if xi = ,q then U’ E X1X1x2x3.. .X, with x’ E (0, l}. Then, Q(u) = xixix2. ..x,, and fizC2.n)(U), i.e. U’ = X2X3 . ..X.X’, ~1~1.~2~3.

@(U’) = x*x*. . .x,x’ = x,x2.. ______.x,x’. Hence, bijection

@ is an homomorphism

In the two cases, (@J(U), @(u’)) E A(B(2,n from ae

into B(2,n + I). Moreover,

and since \A(.%?~)\ = IA(B(2,n + l))I, then K$ is isomorphic

+ I )).

since @ is a

to B(2,n + 1). r_

The construction of B(2, n + 1) from two copies of B(2, n) can also be described as follows. Take in the first copy Bl(2,n) two digraphs TO and Ti, each one made of a tree rooted, respectively, in 0” and I”, with an added loop on the root. The arcs of 7’0 are all the arcs (O’u, Of-’ ux), with x E (0,1}, 1 < i < n - 1 and u E Z!z-‘P ’ such that the first letter of u is 1 if 1~1 > 0. Similarly, the arcs of Ti are all the ones of the form (l’u, l’-‘ux), where the first letter of u is 0 if /u/ > 0. The leaves of the trees in To and Ti are the vertices Olu, with u E Z-‘, and lOu, respectively, i.e. the vertices of V$(B1(2,n)) in the above construction, associated with vertices O*E and 12U, respectively, in V(&(2,n)). But vertices 0% and l*U are the leaves of the double-rooted oriented spanning tree DT, obtained by breadth-first search in Bl(2.n) starting with the double root 0101.. and 1010.. (see Fig. 4). Therefore, B(2, n + 1) can be considered as constructed from the union of To, TI and DT by exchanging

108

D. Barth,

M.-C.

Heydemanni

Discrete

Applied Mathematics

Tl

TO

77 (1996)

& 4 0000

0001

11

0101

I 0011

1111

1110

0010

0100

1101

1100

0110

0111

1000

1001

0001

oooo

1111

1110

I

1010

:

0010

99-118

1011

I 1 01

1 00

[

DT Fig. 4. Digraphs TO,TI and DT in B(2,4),

outgoing of DT.

5.

and induced construction.

arcs from the leaves of trees in TO and TI with outgoing

Composition

arcs of the leaves

of a digraph with its line digraph

In this section we apply the construction of G @$ H to the case where H is the line digraph L(G) and $(x) is an out-going arc of x for any vertex x of G. We then apply this construction to relate Kautz digraphs to de Bruijn digraphs. Let G be a digraph such that for any vertex X, &k(x) 3 1. Let 19be a mapping from V(G) to V(G) such that, for any x E V(G),

O(x) E T;(x).

This mapping

induces

a

mapping $0 from V(G) to V(L(G)), by $(x) = (x, O(x)), for any x E V(G). Let us denote &(G) = G & L(G). Thus, &(G) is the digraph obtained from the union of the two digraphs

G and L(G) by exchanging

for each vertex x of G its out-neighbours

y with the out-neighbours of (x, O(x)) in L(G), i.e. arcs (Q(x),z), for z E r&(0(x)). Thus [email protected](G) has as vertex set V(G) U V(L(G)) and its arcs are of the following three forms: (a) (x,(Q(x),z)), with z E ri(O(x)), for x E V$(G) = V(G), (b) ((x, O(x)), y), with y E T;(x), outgoing from the vertex (x, Q(x)) of V,(L(G)), (c) [(x,Y), (y,z)l from the vertex (x,y)

=

(x,Y,z),

in V(L(G))

We give simple examples

with Y E r&(x>,

y #

@>,

z E r,f(y>,

outgoing

- V,,(L(G)).

of digraphs J&(G).

Example 2. If G = C,,, then Ko(C,,) = C, U C, for n even and Ko(C,) odd.

= C2,, for n

D. Barth, M.-C. Heydemanni Discrete Applied Mathematics 77 (1996) 99-118

Since L(C,,) example

= C,, and +” induces

is the same as Example

an isomorphism

between

109

C,, and L(C’,,), this

1.

Example 3. If G is K:, the complete digraph on two vertices 0, 1, with a loop on each vertex, then there are three possible digraphs Ko(Kc) depending on the choice of mapping 8. There are three possible non-equivalent choices for the mapping 0 (see Figure 5). Case 1: 0(O) = 0, /3(1) = 1. Then $0(O) = 00, $o( 1) = 11. The line digraph of K,f is the de Bruijn digraph B(2,2) and Ko(K,‘) = B(2, l)@ B(2,2) is isomorphic to the Kautz digraph K(2,2). This case is generalized in Corollary 1 below. Case 2: O(0) = 1, Q(1) = 0. Then @o(O) = 01, $~~(l) = 10. Ko(K;) is isomorphic to the generalized de Bruijn digraph G&6,2). This case is generalized in Corollary 2, Section 6. Cuse 3: O(0) = 0, 0( 1) = 0. Then I/Q(O) = 00, &(l) = 10. Kfj(KT) is a strong digraph of diameter 3. Let 0 be a mapping 0 on V(G) such that 0(x) E r:(x) induces

a mapping

Definition

on V(L(G))

1. For any mapping

: (x,y)

for any vertex X. Then, (1

+ (y,B(y)).

19 on V(G),

mapping

flL is defined

on V(L(G))

by

OL((X?v)) = (X Q(Y)). Thus, tIL induces a mapping from V(L(G)) to V(L(L(G))) defined by (x,):) + [(x, v), (y, (9(y))]. The following theorem shows that the operations L and &I( commute.

Bl2,l)

case

1

B(2,2)

case

2

Fig. 5. Possible constructionsfor Kn(Kt).

case

3

D. Barth,

110

Theorem 1. Let

M.-C.

Heydemann

I Discrete

G be a digraph

with 6(G)

V(G) such that, for any x E V(G), isomorphic

Applied Mathematics

77 (1996)

99-118

> 0 and 8 a mapping from

d(x) E r&(x).

Then the line-digraph

V(G)

to

L(Ko(G))

is

to the digraph K~L(L(G)).

Proof. By construction,

the vertices

denoted (x, Y), with Y E r&(x), of G, (x,Y,z),

with Y E r&(x)

of the digraph

Koi.(L(G))

or arcs [(x, Y), (Y,z)] of L(G), and z E r;(Y).

L(G) @A/++ L(L(G)), with $w((x, Y)) = [(x,Y), (v, of Ko(L(G)) are of three types.

are either arcs of G, also denoted as dipaths

Let us recall that K~L(L(G)))

=

@>>I = (x,Y,KY)). Thus,the arcs

(I 1) [(x, Y), (Y, Kv)~z)l, with Y E r,f(x> and z

E ad); (12) [(x,Y,KY)),W)I, with Y E [email protected]), z E C$(Y); (13) 0, Y,z),CJGZ,~N, with Y E [email protected]), z E r&I and z # KY), u E r&I.

In order to prove the theorem we define a mapping f from the set of vertices K+(L(G)) to the set of arcs of Ko(G) considering three different cases of vertices. For Y E r:(x), f(x,Y) = ((~,W)),Y), (~2) For z E [email protected]>>, fk G->,z) = (x, (@),z)), (~3) For Y E [email protected]), Y # @), z E r,f(y), [email protected],y,z)

of

(vl)

= @,y,z).

By definition of the mapping f and of the three types of arcs (a), (b), (c), of Ko(G) we have pointed out at the beginning of the section, f is surjective. Since the digraphs L(Ko(G)) and K+(L(G)) have the same number of vertices, i.e. IA(G)1 + IA(L(G))I, f is bijective. Let us now show that f is arc-preserving. We consider the three types of arcs of K~L(L(G)). (11) BY (~1) and (~21, the arc Nx,~),(y,&y),z)l (Y, (NY)~Z))l~ (12) By (~3) and (vl),

the arc [(x,Y,8(y)),(Y,z)],

is sent by f ontoK(x,@>>,y), with z E T:(y)

onto[k Y,&Y)), ((Y, &Y))G)I. (13) By (v3), the arc [(x,Y,z),(y,z,u)],

with z # 8(y),

is sent by

is sent by

f

f onto [(x,y,z),

(YA u)l. In all cases the image is an arc of L(Ko(G)). If we know that L(Ko(G)) and K~L(L(G)) have the same number of arcs, which is the case if G is regular, then f is an isomorphism and the proof is finished. Otherwise, we can prove that f -' is also arc-preserving. Notice that it is easy to define the inverse mapping f -' considering the 3 types of arcs of Ko(G): (a) For z E r:(Q)),

f-'(x,(Qb)> = (x,@>,z>E W(G)).

@I ForY E [email protected], f-‘((x, Q>h Y) = (x,Y> E V(L(G)). Cc>For Y E r&(x), Y # fXx), z E T$(Y), f-'(x,.w) = ky,z) We consider (al)

five cases depending

For z E r~(@)),

Kx,(G),z)h

(@),z,u)l

(a2) For z E r&(&x)),

E AMG)).

on the type of the arcs of L(Ko(G)).

z # e(Q)) the arc [(x,(@),z)), ((@>,z>,(z,u>>l = is sent by f-' ontoKx,W),z>,(W>,z,u)l. the arc [(x, (e(x), 0(0(x))),

ontoNx,Q(x),QQ(x>)>, (W>, ~11.

((0(x), 0(0(x)), u)] is sent by

f--I

III

D. Burth, M.-C. HeydenzannI Dixwte Applied .Mathrmutks 77 ilY96j 9% I IX

(b) For Y E T:(x),

the arc [((x, O(x)),Y),

[(X>Y )>(Y>H(Y)>u)l. (cl) For Y E T:(x),

y # H(x), z E r:(y),

(_v,(H(Y), u))]

z # Cl’(Y),the arc [(x,,v,z),

sent by .f-’ onto [(x, y,z), (Y,z, v)] = (x, y,z, v). (~2) For Y E T:(x) and u E T;(y), [((x,y,(I(Y)), onto [((x,Y,O(Y)),(y,tl)].

is sent by .f’-’

((Y,O(Y)),u)l

onto

(Y,=,r.)l

is

is sent by .f‘-’

!I

We will now apply our results to de Bruijn and Kautz digraphs. For any positive integer n, and any mapping 0 on &I, we define a mapping

O,, on

V(B(d, n )) by x,)

O,,(X,Q ” According lemma.

= x2 .’

to Definition

Lemma 5. Mapping B(d,n

x,0(x,,).

1 given at the beginning

0,

on B(d,n)

induces

of this section, we get the following

mupping

(In+, on L(B(d,n))

Of; =

=

+ 1).

Proof. By definition @([x,x2

.

of Of;,

xtz,x2

“.

Thus, using the isomorphism ($(x,x2

‘.’ x,x,+,)

=x2

w,I+II) =

[x2



=

b2

. .

between “’

L(B(d,n))

x,x,+,0(x,+,)

-hhz+I, .wGl+

44.~2 I 3 x3

and B(d,n



4Jn+I xnxn+

)I

1 f&G7+

I

)I.

+ l),

= Hn+,(X,X2 “.

X,,Xn*,).

r

The following corollary indicates how K(d, n) can be constructed from B(d, n - I ) and B(d,n) using mapping l3 defined by Q(i) = i, for any i E Z,,. We equivalently define a mapping &-I from V(B(d,n - 1)) to V(B(d, n)) by l+$_,(x I... X,-l) for each XI . ..x.,_I

=

l/?&,(X ,.... r,_,)

E V(B(d,n

= X[...X,_I.X,,_[

- 1)).

Corollary 1. The Kautz digraph K(d,n), 1)). Equivalently, K(d,n) is isomorphic

d > 2, n 3 2, is isomorphic to B(d,n

to Ko_,(B(d,n

- 1) @,b,,_,B(d,n).

Proof. By induction on n. Let us first prove that the property is true for n = 2. Let us recall that L(B(d, 1)) = L(Kd+) = B(d,2). By construction the vertices of Ko(Ki) are all u and all UU, where U, v E Zd. The arcs outgoing from a vertex u E Zd, are all (u, uv). with v E L,; the arcs outgoing from a vertex UU, u E Zd, are all (uu, w), with VYE Z,,. finally, the arcs outgoing from a vertex UC, with u, c E &, u # v, are all (ur, VW). with w E &. To prove that Ko(Ki) = Ko(B(d, I)) is isomorphic to K(d,2), consider the following one-to-one mapping h from V(Ko(B(d, 1))) = V(B(d, 1)) U V(B(d,2)) to V(K(d, 2)).

112

D. Barth, M.-C.

HeydemannIDiscrete

Applied

Mathematics

77 (1996)

99-118

- for u E V(B(d, 1)) = &, h(u) = du, - for u E &, h(uu) = ud, - for 24, v E .Zd, u # u, h(uu) = UU. It is immediate digraphs

that h is surjective

are regular

and therefore

of degree d, it is sufficient

order to prove that K(d,2)

h is bijective.

Since the considered

to verify that h is arc-preserving

and Ko(K,‘) are isomorphic.

in

For this, we consider the image

of the three types of arcs of Ko(K,f ). _ The arc (u, UU), u E Zd is sent by h onto (du,uv). - The arc (uu, w), U, w E Zd is sent by h onto (ud, dw). _ The arc (uu,uw), u, v E &, u # v, is sent by h onto either (uu,vw) (uv,vd) if v = w.

if v # w, or

In each case we get an arc of K(d,2). Assume KS,_, (B(d,n- 1)) = K(d,n), for some y13 2. Since L(B(d,n- 1)) = B(d,n) and L(K(d,n)) = K(d,n + l), by Theorem 1 and Lemma 5, we get K(d,n + 1) = L(K(d, n)) = -GG_, (Nd, n - 1)I = FF_, MNd, n - 1)) = Kon(B(d,n)). This proves that K(d,n)

= Ke,_! (B(d,n - 1)) for all integers

n, with n 3 2. This is equivalent

K(d,n) =B(d,n-l)@,~_,B(d,n), with $fi_i(xl~~...~,_i) vertex XIX~..‘X,_~ of B(d,n - 1). 0

=xix2~~~x,_lx,_i

to

for any

In other words, Corollary 1 says that K(d,n) can be constructed from the union of B(d,n - 1) and B(d,n) by exchanging for each vertex ~1x2.. .x,-l of B(d,n - 1) all its out-neighbours with all the out-neighbours of the vertex ~1x2.. .x,-~x,-~ of B(d,n). In Section 7 we will give an application of this result to k-factors. We will now use Corollary

1 in order to answer the question

settled by J.-L. Fouquet

WI. Proposition

5. There exists a surjective mapping C&from V(K(d,n))

such that the image of the arcs of K(d,n)

onto V(B(d,n))

is composed of all the arcs of B(d,n)

and

of the arcs of a subgraph isomorphic to B(d, n - 1). Proof. By Corollary 1, there exists a subjective mapping fn from V(K(d,n)) onto v(K~~_,(B(d,n - 1))) which is an isomorphism. Consider the mapping gn from V(Ke,_,(B(d,n

- 1))) = V(B(d, n - 1)) U V(B(d,n))

to V((B(d,n))

for x~x~~~~x,-~x,

Sn(XIX2’..X,-lX,)=X1X2...X,-lX,

E

defined by

V(B(d,n))

and gn(xix2...x,-i)

=xtx~~~~x,_ix,_i

for XIX~‘..X,_~

E V(B(d,n-

1)).

By construction, the image of Ko,_, (B(d,n - 1)) by gn is the digraph B(d,n) augmented by the image of the arcs of B(d,n - l), which are the arcs (xix2 . ..x._ix,-1, x2 . . .x,_Ix,x,,) corresponding by construction to the arcs (x1 . . .x,_l,x2 . . .x,) in

D. Barth, M.-C. Heydemann IDiscrete Applied Mathematics 77 (1996)

B(d,n - 1). By composing fn and g,, we obtain satisfies the announced property. 0

a mapping

99- I18

I#I~ = gn o

113

fn which

Remark 3. The previous result was also shown by J.-L. Fouquet in the case of diameter 2 [12]. He asked for a generalization answer to this question $,, are detailed

of his result to any diameter.

in Proposition

5. Expression

We give a positive

and some properties

of mapping

in [2].

In fact, the original

problem

was the partition

of the arcs of de Bruijn

and Kautz

digraphs into l-factors in which all cycles other than loops have an even number of arcs. This was motivated by the determination of the chromatic index of these digraphs. This is now solved in [4], but without using any relation between the two families of digraphs.

6. Application

to the generalized

de Bruijn digraph

Corollary 1 shows two families of iterated line digraphs, de Bruijn and Kautz digraphs, such that the second one is obtained from the first one by using operation & for some mapping 0. One can ask about other families with the same property. Since by Propositions 1 and 2, some generalized de Bruijn and Kautz digraphs can be obtained by line digraph iteration, the following problem arises. Problem 1. Does there exist a mapping such that Kfr(GB(N,d))

= GB(N,d)

8 : x E V(GB(N,d))

c$,,~ GB(dN,d)

+ e(x) E r&(h’,C,j(~~)

= II((d + l)N,d)?

By Corollary 1, the answer to Problem 1 is yes in the case N = d”-’ since B(d. II 1) = GB(d”-‘,d) and K(d,n) = ZI((d + 1 )dn-‘,d), but the following example shows that the answer is no for N = 3 and d = 2. Lemma 6. For any mapping 0 : x E V(GB(3,2)) is neither isomorphic to II(9,2) nor to GB(9,2).

+ H(x) E T&3.2)(x),

&(GB(3,2))

Proof. The proof is by exhaustive construction of &(GB(3,2)). There are eight possible mappings 0 from Z3 into Zs. By symmetry of GB(3,2), only four different digraphs Ke( GB(3,2)) have to be considered and compared to 11(9,2) and GB(9,2). 0 Notice answer.

that a more general

problem

is the following

one, for which we have no

D. Barth, M.-C. HeydemannlDiscrete

114

Problem 2. Does there exist a mapping

Applied Mathematics 77 (1996)

$ from

99-118

V( GB(N, d)) into V( GB(dN, d)) such

that GB(N, d) @+ GB(dN, d) = ZZ((d + 1)N, d)? On the other hand, if we replace

in Problems

digraph GB((d + l)N,d), some answers induce the following corollary.

1 and 2 digraph ZZ((d + l)N, d) by

are given below.

First, results

of Section

5

Corollary 2. GB(3 .2”, 2) = Ko,(B(2, n)) = B(2, n) @$,ji/o, B(2, n + 1) for 0(O) = 1, 0( 1) = 0, and equivalently $o~(x~x~ . . .x,) = ~1x2.. ~x,_lx,,X,. Proof.

By Example 3(2), &(K,f)

= Ko(B(2,l))

sition 1 and Lemma 5, we get &.(B(2,n)) L”-‘(GB(3 .2,2)) = GB(3.2”,2). 0

= GB(6,2).

= &“(L”-‘(B(2,l)))

So, by Theorem

1, Propo-

= L”-‘(&(B(2,1)>>

=

Corollary 2 gives a positive answer to the new problem for N = 2” and d = 2, but Lemma 6 shows that the answer is no for some other values of d. Despite this, the generalized de Bruijn digraphs verify some iterated construction if N is a multiple of 6. Let us define the following application t,k $ : V(GB(2N,2)) i

+ V(GB(4N,2)), + N+i,

Proposition 6. For each integer N 3 1, GB(2N,2) C$ GB(4N,2) is isomorphic GB(6N,2) and mapping $ is not induced by a mapping 0 : x E V(GB(2N,2))

to +

O(x) E Z&N,2)(X). Proof. Let us define an application @ from V(GB(2N,2)) U V(GB(4N,2)) V(GB(6N,2)) such that for each j E V(GB(2N,2)) U V(GB(4N,2)),

Q(j) =

into

if j E V(GB(4N, 2))and j < 2N,

.i j + 2N

if j E V(GB(4N, 2))and j 3 2N,

j + 2N

if j E V(GB(2N,2)).

It is easy to see that @ is a bijective

mapping

V( GB(6N, 2)). Let us now show that @ is also arc-preserving.

from V(GB(2N,2)@,

GB(4N,2))

into

We consider three cases of arcs (x, y) E

A(GB(ZN, 2) gccl GB(4N, 2)). First, x E V(GB(2N,2)).

Then, y E r&dN,2)(ti(x)), i.e. y = 2(N +x> fr G(x) = x + 2N and ifx
r E (0,1). By definition, l l

[4N] with

D. Barth, M.-C. Heydemann I Discrere Applied Muthenluticx

Secondly,

x E V(GB(4N,2))

and y E V(GB(2N,2)).

77 (19%

J 99

I18

115

Then x = N + i with 0 < i < 2N

and y E I&,,v_,,(t,!-l(x)). So y E 2i + r [2N] and l if i < N then Q(x) = N + i and Q(y) = 2N + 2i + Y, l

if i = N + i’ then Q(x) = 4N + i’ and Q(y) = 2N + 2i’ + I’.

Third, x E V(GB(4N, 2)) and y E V(GB(4N,2)). l l

Then, x < N or x 3 3N.

if x < N, then y = 2x + r < 2N, Q(x) =x and @(J,) = J’, if x = 3N +x’ then y = 2N + 2x’ + r, Q(x) = x’ + 5N and G(y) = 2.x’ + 4N + I..

Hence, in all cases (Q(x), Q(y)) E A(GB(6N,2)) an d so @ is an arc-preserving mapping. So since @ is a bijection and since ~A(GB(~N,~)~Z&I,GB(~N,~))~ = lA(GB(6N.2))1. then GB(2N, 2) 8,~ GB(4N,2) is isomorphic to GB(6N,2). We now prove by contradiction that mapping $ is not induced by a mapping 0 : .x E V(GB(ZN,Z)) + t)(x) E ~&~2,v,2~(x). If not, we could find mappings (1 and r such that 0(i) E 2i + r(i) [2N], with r(i) E (0, I}, and an isomorphism sending (i, H(i)) of GB(2N,2) onto the vertex $(i) of GB(4N,2). By the construction after Proposition 1 where (i, 0(i)) is associated with 2i + r(i) E V(GB(4N,2)), equivalent to find an isomorphism h of GB(4N.2) such that h(2i+r(i)) E i+ N [4N]. If i < N, then h(2i + r(i)) = N + i. We consider two cases depending

the arc given this is = li/( i) on the

value of V( I ). l If~(l)=Owegeth(2~1+r(l))=h(2)=N+l andh(4+v(2))=N+2.Since vertices 2 and 4 + r(2) are adjacent in GB(4N,2), but vertices N + 1 and N + 2 are not, this contradicts the arc-preserving property of h. l If I( 1) = 1, we get a similar contradiction by considering h(2.1 + Y(I )) = h(3) = N + 1 and h(2.3 + r(3)) = N + 3. r’ Remark 4. Notice that mapping $~~o, of Corollary 2 induces by isomorphism of B(2, n), B(2, n + 1) and GB(2”,2), GB(2 ‘+’ , 2), respectively, a mapping $’ from V(GB(2”, 2)) to V(GB(2”+‘, 2)), such that $‘(i) = 2i + i mod 2, for any i t Zp = V(GB(2”,2)). This mapping is different from mapping $ given in Proposition lb(i) = 2”-’ + i. But by Corollary 2 and Proposition 6, we have GB(2”,2) cf$ GB(2”+’ ,2) = GB(2”,2)@,/,,GB(2”+‘,2) This shows that two different

mappings

6, which

satisfies

= GB(6.2+‘,2).

$ can lead to the same composed

digraph

G cab H.

7. Application

to k-factors

A i-jbctor of a digraph G, with i < d(G), is a i-regular spanning subgraph of G [3]. The number of different l-factors in G is an interesting parameter in the following way. Consider that G represents an interconnection network of a parallel architecture [13]: each vertex models a processor and an arc is an unidirectional link from one processor to another one. We consider a l-port oriented hypothesis of communication

116

D. Barth, M.-C.

HeydemannlDiscrete

Applied Mathematics

77 (1996)

99-118

in this network: at each communication step, each vertex can send a message most one successor, and it can receive a message from at most one predecessor. To implement

efficient parallel algorithms

to be considered

communication

pattern

is the routing of permutations [21]. Let p be a permutation p in G consists

V(G). Routing

in G, one important

to at

for each i E V(G) to send a message

on

to p(i). Such

p on V(G) is said to be at distance I in G, if for each i E V(G),

a permutation

distc(i,p(i)) = 1 (or distc(i,p(i)) < 1 if there is a loop on i). We denote by Y,(G) the set of permutations at distance 1 in G. Notice that permutations at distance 1 in G are permutations p which can be routed in 1 communication step in G; during this step, each vertex r sends a message on (v, p(v)) and receives a message on (p-‘(v), u). The digraphs induced by the arcs used in the routing is a l-factor of G. Hence, there is a direct bijection between Y,(G) and the set of l-factors of G. We will so especially focus on l-factors in digraphs. We first give a general result about i-factors; then, we deal with the number of l-factors in de Bruijn and Kautz digraphs. Consider

99 a digraph,

denote by 3i(Y) Proposition Proof.

and an involutive

the set of all the i-factors

mapping

4 :

V(3)

+

7. For each i 2 1, S+ de&es a bijection between 3i(9)

Consider

V(9).

Let us

of 9.

first g E 3i(C!2), with i 3 1. Then by definition,

and 3i([email protected](g)). for all u E V(g),

6:(v) = 6;(u) = i. Let u be a vertex of V(g) = V(9): _ by Remark 1, 6&r,(u) = 6&)(o) = i, - UZ&J)) - 4%(S))

= I%%$(~)), c4%(~))-

Hence, S+dg) E 345dW)

and so Sb defines an application from 3i(Y) into and also from 3i(S’~(~)) into 3i(Y) by symmetry since SC’ = S,. More-

3i(Sd(9)),

over, since for all g E 3i(‘S), 349)

and 34X++(%)).

S&$,(g))

= g, then S, defines

a bijection

between

0

Remark 5. Proposition 7 cannot give a positive answer to the problem we introduced in Remark 2. The problem of the factorization into l-factors in which all cycles other than loops have an even number of arcs cannot be handled with our results. For example the even l-factors (written as cycles) (0,l) of B(2,l) and (00,01, 1 1,lO) of B(2,2) give by @$ for $(O) = 00, $(l) = 11, two 3-cycles, (Ol,ll,O) and (lO,OO, l), of B(2,l) @$ B(2,2) = K(2,2). It would be interesting to find a condition on even l-factors of B(d,n) in order that they give even l-factors of K(d,n) by @ Proposition (

&d”-’

8. For all d > 1 and n > 0, 13l;(B(d,n))l = dP”-’

dil

>

ifn

>

1, else 13l(K(d, 1)) = d! C~zO(-l)‘/i!.

and I.?(K(d,n))l

=

D. Barth, M.-C. Heydemannl Discrete Applied Mathernaric.s 77 (1996)

99- 118

117

Proof. (1) If d > 1, B(d, 1) is isomorphic to the complete symmetric digraph with a loop on each vertex KT. It is easy to see that Ppl(KT) = X,1 (the set of all permutations and thus l.7=1(B(d,l))l = lPp~(Kd+)l= d!. 3 and 7, for d > 1 and n > BY Propositions

on &)

(2)

1, l.F~(B(d,n))l

= /F’I(~)!,

Y is the union of d copies of B(d,n - 1). SO, IFl(B(d,n))l = d!d’l-‘. n - 1))l”. Hence, by induction on n, we show /3l(B(d,n))l Corollary 1 and Proposition 7, for d > 1 and n > 1, (3) BY

=

where

lF(K(d,n))l = I.F;(B(d,n))lx IJ=l(B(d> n

Note at end that since K(d, 1) is isomorphic all permutations of derangements

_

I))1

=

(31(&d,

(df-‘)“+‘,

to E;d* and .Yi(Ki)

without fixed elements on V(K,*), then I3l(K(d, on d elements, i.e. d! cfz, (-l)‘/i! [6]. 0

is clearly l))l

the set of

is the number

Proposition 8 just computes the numbers of l-factors in de Bruijn and Kautz digraphs. But the construction we give in the proof of this proposition can also be used to determine a characterization of 91(B(d,n)) and of .?,(K(d,n)) from one of .Y,(K,+).

8. Conclusion In this article we have defined a new operation S$ on digraphs and we have proved some properties of this operation. We have applied it to different cases and obtained results on the construction of de Bruijn, generalized de Bruijn and Kautz digraphs. In Table

Table

1, we summarize

the constructions

we give in the previous

sections.

I

Digraph

g

Digraph

S$(Y)

See

de Bruijn digraphs, d-1 U B(d,n) with d > I, n > 0 ,=
de Bruijn digraph B(d.n + I)

Proposition

3

de Bruijn digraphs, B(2,n) u B(2,n),

de Bruijn diyaph B(2.n + 1)

Proposition

4

de Bruijn dlgraphs, B(d.n) u B(d.n + l), with d > 1, n > 0

Kautr digraph K(d,n + 1)

Proposition

5

Gen. de Bruijn digraphs, GB(2N,2) U GB(4N,2),

Gen. de Bruijn digraph GE( 6/v, 2)

PropositIon

6

Butterfly digraphs [GBi(d,n))”

with n > 0

with N > 0

Butterfly digraph

and copies of Kdf, [iKJ),withd>

I,n>O

BF(d,n*l)

Remark 2

D. Barth, M.-C. Heydemann IDkcrete

118

We have also related k-factors

Applied Mathematics 77 (1996)

of a digraph

This allowed us to obtain inductively

3 to k-factors

the number

of l-factors

99%118

of the digraph

B(d, n) and to deduce the number of l-factors of the Kautz digraph K(d, n). Some problems remain open. For example, we did not find an extension generalized

de Bruijn and Kautz digraphs of our construction

from de Bruijn

digraphs B(d,n)

and B(d,n

$(3).

of the de Bruijn digraph to all

of Kautz digraphs K(d, n)

- 1).

Acknowledgements The’ authors thank J.-L. Fouquet for introducing them to the problem solved in Proposition 5 and which motivated this article. They are also grateful to J.-L. Fouquet, D. Sotteau and R. Harbane

for helpful discussions

on the same problem.

References [ll

VI 131 141 [51

[cl [71 PI [91

F. Annexstein, M. Baumslag and A.L. Rosenberg, Group action graphs and parallel architecture, SIAM J. Comput. 19 (3) (1990) 544-569. D. Barth and M.-C. Heydemann, A new digraphs composition, Research Report 1019, LRI, Universite de Paris&d, Orsay (1995). C. Berge, Graphes et Hypergraphes (North-Holland, Amsterdam, 197 1). J.-C. Bermond and P. Hell, On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs, J. Graph Theory 17 (1993) 647-655. J.-C. Bermond and C. Peyrat, De Bruijn and Kautz networks: A competitor for the hypercube? in: F. Andre and J. P. Verjus, Eds., Hypercube and Distributed Computers (Elsevier, North-Holland, 1989) 2799493. N.G. Biggs, Discrete Mathematics (Oxford Science Pub]., Oxford, 1985). 1. Bond, Grands reseaux d’interconnexion, Ph.D. thesis, Universite de Paris&d, Orsay (1987). N.G. de Bruijn, A combinatorical problem, Koninklijke Nederlandsche Akademie van Wetenschappen Proc., Vol. A49 (1946) 7588764. 0. Collins, S. Dollinar, R. McEliece and F. Pollara, A VLSI decompostion of the de Bruijn graph, Intern report, Department of Elec. Engen., California Institute of Technology (1989). D.Z. Du and F.K. Wang, Generalized de Bruijn digraphs, Networks 18 (1988) 27-38. M.A. Fiol, J.L.A. Yebra and 1. Alegre, Line digraph iterations and the (d,k) digraph problem, IEEE Trans. Comput. C-33 (1984) 400-403. J.L. Fouquet, private communication (199 I ). P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Discrete Appl. Math. 53 (1994) 799133. H. Fredricksen, A new look at the de Bmijn graph, Discrete Appl. Math. 37/38 (1992) 193-203. M. Imase and M. Itoh, A design to minimize diameters on building bloc network, IEEE Trans. Comput C-30 (1981) 439-442. N. Homobono, Fault tolerant routings in Kautz and de Bruijn networks, Annex of thesis, Universite de Paris-Sud, Orsay (1987). W.H. Kautz, Bounds on directed (d,k) graphs, Theory of cellular logic networks and machines, AFCRL-68-0668 Final Report (1968) 20-28. M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Application, Vol. 17 (Addison-Wesley, Reading MA, 1983). J. de Rumeur, Communications dans les reseaux d’interconnexion (Masson, Paris, 1994). M.R. Samathan and D.K. Pradhan, The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI, IEEE Trans. Comput. C-38 (1989) 5677581. L.G. Valiant, A scheme for fast parallel communication, SIAM J. Comput. 11 (1982) 350-361. J.L. Villar, The underlying graph of a line digraph, Discrete Appl. Math. 37/38 (1992) 525-538.