Mean Eccentricities of de Bruijn Networks Jean-Claude Bermond, 1 Zhen Liu, 2 Michel Syska 1 1 SLOOP, Joint Project 13S-CNRS/UNSA/INRIA, 2004 Route des Lucioles, BP 93, F-06902 Sophia-Antipolis, France 2 2004 Route des Lucioles, BP 93, F-06902 Sophia-Antipolis, France Received 6 August 1993; accepted 28 February 1997 Abstract: Given a graph G Å (V, E), we define eV ( X ), the mean eccentricity of a vertex X, as the average distance from X to all the other vertices of the graph. The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper, we consider upper and lower bounds for eV ( X ). For the directed de Bruijn network, we provide tight bounds as well as the extremal vertices which reach these bounds. These bounds are expressed as the diameter minus some constants. In the case of undirected networks, the computation turns out to be more difficult. We provide lower and upper bounds which differ from the diameter by some small constants. We conjecture that the vertices of the form arrra have the largest mean eccentricity. Numerical computations indicate that the conjecture holds for binary de Bruijn networks with diameters up to 18. We also provide a simple recursive scheme for the computation of the asymptotic mean eccentricity of the vertices arrra. Finally, we prove that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of arrra is smaller than a small constant tending to zero with the degree. A byproduct of our analysis is that in both directed and undirected de Bruijn networks most of the vertices are at distance near from the diameter and that all of the mean eccentricities (and therefore the average distance) tend to the diameter when the degree goes to infinity. q 1997 John Wiley & Sons, Inc. Networks 30: 187–203, 1997 Keywords: interconnection network; de Bruijn network; distances; mean eccentricities; bounds 1. INTRODUCTION AND NOTATION Graphs are widely used in the design and analysis of computer networks. A vertex in the graph denotes a node or processor in the corresponding network, and an edge denotes a communication link between two nodes. If a network is unidirectional, i.e., the communication links in the network are unidirectional, a digraph (i.e., directed graph) is used, whereas for a bidirectional network, an undirected graph (or simply, graph) is used. Let G Å (V, E) be a (strongly) connected graph (or digraph), where V denotes the set of vertices, and E, the set of edges (or arcs for digraphs). We will denote by N Å ÉV É the number of vertices in G. The vertex X is a neighbor of the vertex Y if (X, Y ) √ E or (Y, X ) √ E. The degree of a vertex is the number of its neighbors. The degree of a graph is the maximum degree of the vertices. In case of a digraph, we can distinguish the predecessors and successors of vertex X, which correspond to the neighbors Y which satisfy (Y, X ) √ E and (X, Y ) √ E, respectively. The number of arcs entering (respectively, going out from) a vertex X is called the q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/030187-17 187 / 8U16$$0780 08-19-97 19:15:05 netwas W: Networks 780 188 BERMOND, LIU, AND SYSKA Fig. 1. Example of a de Bruijn digraph B(2, 3). in-degree (respectively, out-degree) of X. The in-degree (respectively, out-degree) of a graph is the maximum indegree (respectively, out-degree) of the vertices. A path (respectively, a dipath) between two vertices X and Y (respectively, from X to Y ) in a graph (respectively, a digraph) G is a sequence of vertices {X Å X1 , X2 , . . . , Xk Å Y } such that two consecutive vertices in the sequence are joined by an edge (respectively, an arc). The length of a path is the number of edges on this path. The length of a shortest path (respectively, dipath) between X and Y (from X to Y ) is called the distance and is denoted by d(X, Y ). Note that in the case of digraphs it is not a classical distance as d(X, Y ) might be different from d(Y, X ). The diameter of a graph is the maximum distance in the graph. The de Bruijn digraph (respectively, graph), denoted by B(d, D) [respectively, UB(d, D)], has N Å d D vertices with diameter D and in-degree or out-degree d (respectively, degree 2d). The vertices correspond to the words of length D over an alphabet of d symbols. The arcs (or edges) correspond to the shift operations: Given a word X Å x1rrrxD on an alphabet A of d letters, where xi √ A, i Å 1, 2, . . . , D, and given l √ A, the operation • x1rrrxD r x2rrrxDl is called a left shift; • x1rrrxD r l x1rrrxD01 is called a right shift. In the de Bruijn digraph B(d, D), the successors are obtained by left-shift operations, whereas in the de Bruijn graph UB(d, D), the neighbors are obtained by either left- or right-shift operations. An example of a de Bruijn digraph is given in Figure 1. The corresponding undirected de Bruijn graph is obtained by transforming arcs to edges (i.e., removing the directions of the arcs) and removing the redundant edges (i.e., those with multiple occurrences in the graph or those linking the same vertices). The multiprocessor system which can be modeled by a de Bruijn graph is called a de Bruijn network. The reader can see that in B(d, D) each vertex has in-degree and out-degree d and there are Nd arcs, whereas / 8U16$$0780 08-19-97 19:15:05 in UB(d, D), there exist N 0 d 2 vertices of degree 2d, d 2 0 d vertices of degree 2d 0 1, and d vertices of degree 2d 0 2. These networks have been discovered by many authors and are named after de Bruijn [8]. They are sometimes also called Good graphs [10]. De Bruijn networks present many attractive features. In particular, they are among the best-known networks for a given degree and diameter [see the survey [2] for more details on this problem known as the (d, D) or ( D, D) graph problem]. They have good vulnerability properties, being able to tolerate up to d 0 1 faults in the directed case and 2d 0 3 in the undirected case, while the diameter can still be left small (see [3]). They are adequate for various applications as one can embed in them linear arrays, rings, and complete binary trees. They can also emulate without loss of time shuffle-exchange or hypercubes for the class of ascend–descend algorithms. De Bruijn networks have also many other interesting properties like easy greedy routing. This greedy algorithm is a simple D-step routing which consists of unidirectional shifts or ‘‘bit-erosion’’ of the destination address; namely, in order to go from X Å x1rrrxD to Y Å y1rrryD , we apply D left shifts (and also right shifts in the undirected case), introducing successively the letters y1 , y2 , . . . , yD , corresponding to the dipath x1rrrxD r x2rrrxD y1 r x3rrrxD y1 y2 r rrrr y1rrryD . We refer the reader to one of the two recent surveys concerning de Bruijn networks written by Bermond and Peyrat [5] and Samatham and Pradhan [14] or to the recent book of Leighton [11]. In this paper, we analyze the mean eccentricity of these graphs. The eccentricity of a vertex X is defined [7] as the distance to the farthest node from this vertex: e(X ) Å max{d(X, Y ) : Y √ V }. We define the mean eccentricity of a vertex X, denoted eV ( X ), as the average distance from X to all the others vertices: eV (X ) Å 1 N01 ∑ d(X, Y ). (1) Y √ V0 {X } The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper, we consider the upper and lower bounds of eV ( X ). In Section 2, we analyze the directed de Bruijn networks. We provide the tight bounds as well as the extremal vertices which reach these bounds. These bounds are expressed as the diameter minus some constants. In Section 3, we analyze the undirected networks. The computation turns out to be more difficult. We provide netwas W: Networks 780 189 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS lower and upper bounds which differ from the diameter by some small constants. We conjecture that the vertices of the form arrra have the largest mean eccentricity. Numerical computations indicate that the conjecture holds for binary de Bruijn networks with diameters up to 18. We will show that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of arrra is smaller than 0.22. We also provide a simple recursive scheme for the computation of the asymptotic mean eccentricity of the vertices arrra. A byproduct of our analysis is that in both directed and undirected de Bruijn networks most of the vertices are at distance near from the diameter and that all of the mean eccentricities (and therefore the average distance) tend to the diameter when the degree goes to infinity. Our results also imply that optimal routing algorithms are in most of the cases not advantageous due to their overheads. Instead, one can use the simple D-step routing algorithm as described above. The following formulas will be extensively used in this paper: p d p/ 1 0 1 . ∑d Å d01 kÅ0 k (2) of a (di)graph G rooted at vertex X a spanning tree of G with root X such that the (di)path in the tree from X to any vertex is a shortest (di)path in G. It can be obtained, e.g., using the ‘‘breadth first’’ search algorithm. Observe that for any given G and X this tree is not unique. However, the vertices at level l of a shortest path tree of G rooted at vertex X are exactly all the vertices that are at distance l from X in G. Therefore, the weights of the shortest path trees rooted at vertex X are identical. The mean eccentricity of a vertex is, in fact, the weight of a shortest path tree rooted at this vertex divided by N 0 1. Let lk (X ) be the width, i.e., the number of vertices, at level k in the shortest path trees rooted at vertex X. Then, D eV (X ) Å 1 ∑ krlk (X ). N 0 1 kÅ1 (4) We first look at the minimal mean eccentricity. We will need the following for the comparison result. Lemma 2.1. Let n be a positive integer, and m1 , . . . , mn , positive real numbers such that n p ∑ kd k0 1 kÅ1 (p / 1)d p d p/ 1 0 1 Å 0 d01 (d 0 1) 2 Å pd p/ 1 0 (p / 1)d p / 1 . (d 0 1) 2 1 ° n ° D 0 1, ∑ mk ° N 0 1. kÅ1 (3) If for all 1 ° k ° n, lk (X ) ° mk , then n eV (X ) ¢ n / 1 0 2. DIRECTED CASE In the case of a digraph B(d, D), it is well known (see, e.g., Fiol et al. [9]) that there is a unique shortest dipath from a given vertex X Å x1rrrxD to a vertex Y Å y1rrryD . To find the distance d(X, Y ) and the shortest dipath, one has to find the smallest i such that xi/1rrrxD Å y1rrryD0i . The distance is then i, and the shortest path is obtained by doing the left shifts introducing successively yD/10i , . . . , yD . This fact allows one to compute easily d(X, Y ) and so eV ( X ) for any X. But, unfortunately, that does not give a closed formula. In this section, we provide upper and lower bounds of the mean eccentricities of B(d, D) and show that these bounds are reached. Our analysis will need some notions on trees (or, more precisely, the outtrees). The level of a vertex in a tree is the distance from the root to the vertex, where by convention, the root is at level 0. The weight of a tree is the sum of the levels of all vertices. We call a shortest path tree / 8U16$$0780 08-19-97 19:15:05 1 ( ∑ (n / 1 0 k)mk ). N 0 1 kÅ1 (5) Proof. Let mn/1 Å N 0 1 0 ( nkÅ1 mk , and mi Å 0 for all n / 1 õ i ° D. It then follows that D D kÅ1 kÅ1 N 0 1 Å ∑ lk (X ) Å ∑ mk and that for all 2 ° i ° D D D i0 1 kÅi kÅ1 kÅ1 ∑ lk (X ) Å ∑ lk (X ) 0 ∑ lk (X ) ¢ Thus, according to (4), netwas W: Networks 780 D i0 1 D kÅ1 kÅ1 kÅi ∑ mk 0 ∑ mk Å ∑ mk . 190 BERMOND, LIU, AND SYSKA D eV (X ) Å 1 ∑ krlk (X ) N 0 1 kÅ1 Å 1 ∑ ∑ lk (X ) N 0 1 iÅ1 kÅi ¢ 1 ∑ ∑ mk N 0 1 iÅ1 kÅi Å 1 ∑ kmk N 0 1 kÅ1 Å 1 ( ∑ kmk / (n / 1)(N 0 1 0 ∑ mk )) N 0 1 kÅ1 kÅ1 D D D D D n n n Ån/10 1 ( ∑ (n / 1 0 k)mk ). N 0 1 kÅ1 j Proposition 2.1. For any d ¢ 2 and D ¢ 2, and for all X Å x1rrrxD √ B(d, D), eV (X ) ¢ D 0 d d D / r . 2 (d 0 1) d01 N01 (6) Moreover, the equality holds if and only if xi x xD for all i Å 1, . . . , D 0 1. Proof. The minimal mean eccentricity corresponds to the shortest path tree with the minimal weight, which, owing to Lemma 2.1, requires that as many as possible vertices should be put in the smallest levels. Since B(d, D) has out-degree d, a vertex has at most d vertices at distance 1, and so d 2 vertices at distance 2, . . . , and d k vertices at distance k. Therefore, in the shortest path trees, there are at most d k vertices at level k, k Å 1, 2, . . . , D 0 1. As 1 / d / d 2 /rrr/ d D01 Å (d D 0 1)/(d 0 1) we have still at least x Å d D 0 [(d D 0 1)/(d 0 1)] vertices which are at level D. Figure 2 illustrates such a tree for the case d Å 2. Therefore, we can apply Lemma 2.1 with n Å D 0 1 and mk Å d k for 1 ° k ° D 0 1: D0 1 eV (X ) ¢ D 0 Å D0 Å D0 1 ( ∑ (D 0 k)d k ) N 0 1 kÅ1 S D D D/ 1 d 0 d Dd 1 d 0d D 0 / N01 d 0 1 d 0 1 (d 0 1) 2 D We now look at the upper bound of the mean eccentricities. We will need the following property of the shortest path tree with the maximal weight. An example is given for the case d Å 2 (Fig. 3). D D kÅi kÅi ∑ lk ° ∑ d k0 1 (d 0 1) ∀i, 1 ° i ° D, Assume now the vertex X Å x1rrrxD is such that xi x xD for all i Å 1, . . . , D 0 1. We want to show the equality in (6). Indeed, for all 1 ° k ° D 0 1, the 08-19-97 19:15:05 vertices at distance k from x1rrrxD are of the form xk/1rrrxD y1rrryk , where y1rrryk are arbitrary letters of the alphabet A. For all 1 ° j õ k , the vertices at distance j from x1rrrxD are of the form xj /1rrrxD0k/jrrrxDz1rrrzj , where z1rrrzj are arbitrary letters of the alphabet A. Since xD0k/j x xD , none of the vertices xk/1rrrxD y1rrryk are at distance j õ k. Thus, the width of the shortest path tree of X at level k, 1 ° k ° D 0 1, is d k , so that the equality in (6) holds. Assume now that for some vertex X Å x1rrrxD the equality in (6) holds. Then, necessarily, the width of its shortest path tree at level D 0 1 is d D0 1 , so that all the vertices at level D 0 1 which have the form xD y1rrryD01 should not already be at levels k Å 0, . . . , D 0 2, where y1rrryD01 are arbitrary letters of the alphabet A. Thus, for all k Å 0, . . . , D 0 2, we should have xk/1 x xD , which completes the proof. j Lemma 2.2. An outtree of out-degree d with d D vertices and D levels is such that d d D / r . 2 (d 0 1) d01 N01 / 8U16$$0780 Fig. 2. Shortest path tree with the minimal weight. where lk is the number of vertices at distance k from the root. Proof. Suppose that the lemma is not true and let i 0 D D be the largest i ¢ 1 such that ( kÅi lk ú ( kÅi d k01 (d 0 1). netwas W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS D Then, li0 ú d i001 (d 0 1), which, in turn, as the out-degree is d, implies li001 ú d i002 (d 0 1), which further implies that li002 ú d i003 (d 0 1), and so on. Therefore, D D D ∑ ∑ lk (X ) ° ∑ ∑ d k0 1 (d 0 1) iÅ1 kÅi iÅ1 kÅi D Å (d 0 1) Å (D / 1)d D 0 D D which, together with the fact that ( kÅi l ¢ 1 / ( kÅi d k01 (d 0 k 0 0 1), imply that Å Dd D 0 D kÅ1 kÅ1 ∑ lk ¢ i 0 / ∑ d k01 (d 0 1) Å i 0 / d D 0 1 ¢ d D . eV (X ) ° D 0 1 D / . d01 N01 We now show that 1 D / . eV (X ) ° D 0 d01 N01 (7) Moreover, the inequality becomes equality if and only if X Å arrra, where a √ A. Proof. Note first that D N01 / D. d01 Therefore, Proposition 2.2. For any d ¢ 2 and D ¢ 2, and for all X √ B(d, D), D d D/ 1 0 1 d01 dD 0 1 d01 Å D(N 0 1) 0 This contradicts the fact that the tree has d D vertices. (Note that the root which is at level 0 is not included in the above summation.) j eV (X ) Å ∑ kd k0 1 kÅ1 li ¢ d i01 (d 0 1) / 1, 1 ° i ° i 0 0 1, D 191 D 1 1 ∑ krlk (X ) Å ∑ ∑ lk (X ). N 0 1 kÅ1 N 0 1 iÅ1 kÅi It follows from Lemma 2.2 that eV (X ) Å D 0 1 D / d01 N01 if and only if X Å arrra. First, the vertices at distance k from arrra are of the form a1rrraD , with a1 Årrr Å aD0k Å a, aD0k/1 Å aV where aV x a and aD0k/2 , . . . , aD can be any letter of the alphabet A. None of these vertices are at distance j õ k. Their number is d k0 1 (d 0 1), so that all the inequalities in the above derivation of the proof become equalities. Second, by Lemma 2.2, a necessary condition for eV ( X ) to reach the bound is that l1 Å d 0 1. Only the the vertices arrra have this property. j The following properties are immediate consequences: Corollary 2.1. For any d ¢ 2 and D ¢ 2, and for all X √ B(d, D), D0 d d D / r (d 0 1) 2 d 0 1 N 0 1 1 D ° eV (X ) ° D 0 / . d01 N01 (8) In particular, when d Å 2, D02/ Fig. 3. Shortest path tree with the maximal weight. / 8U16$$0780 08-19-97 19:15:05 netwas 2D D ° eV (X ) ° D 0 1 / . N01 N01 W: Networks 780 (9) 192 BERMOND, LIU, AND SYSKA Applying R to the vertex X Å x1rrrxD yields vertex arrrra1 x1rrrxD0r , which corresponds to the path Corollary 2.2. lim eV (X ) Å D, D ¢ 2. dr` x1rrrxD r a1 x1rrrxD01 r a2a1 x1rrrxD02 r 1 ° lim inf (D 0 eV (X )) d01 Dr` rrrr arrrra1 x1rrrxD0r . ° lim sup (D 0 eV (X )) ° Dr` d , (d 0 1) 2 d ¢ 2. Our results indicate that the upper and the lower bounds of the mean eccentricities are both close to the diameter. This is especially true when the degree of the de Bruijn network is large. In [12], a linear (in time and in space with respect to the diameter) algorithm was proposed for the optimal routing of directed de Bruijn networks. However, even if we use D shifts to route instead of the optimal routing, the global communication delay of the network should not be affected too much. The routing scheme in D steps corresponds to a simple ‘‘bit-erosion’’ of the destination address, a very simple routing function that could be implemented with only a very few VLSI components on chip. 3. UNDIRECTED CASE We now consider the mean eccentricities of UB(d, D). It turns out that the computation of bounds is much more difficult. This is partially due to the facts that the shortest paths are, in general, not unique and that the determination of the distances between the vertices is more complicated. In what follows, we will first study some properties of the shortest paths in undirected de Bruijn networks. We then derive the lower and upper bounds, respectively. 3.1. Characterization of the Shortest Paths Since the neighborhood in UB(d, D) can be defined by the left- and right-shift operations, a path can be described by a sequence of corresponding shifts. The length of a path connecting X to Y is equal to the cardinality of this sequence of shifts. Formally, let L be the operation consisting of a sequence of l left shifts, introducing a suffix B Å b1 , . . . , bl with É LÉ Å l, and let R be the operation consisting in a sequence of r right shifts, introducing a prefix A Å arrrra1 with É RÉ Å r. Then, applying L to a vertex X Å x1rrrxD yields vertex xl/1rrrxDb1rrrbl , which corresponds to the path In general, any path of the de Bruijn graph can be denoted by L1 R1 L2 R2rrrLn Rn with É Li É Å li and É Ri É Å ri , meaning that we successively apply L1 , then R1 , then L2 , and so on. The length of the path is equal to l1 / r1 / l2 / r2 /rrr ln / rn . Note that one can have l1 Å 0 or rn Å 0. We will use the following results established by Bond [6, p. 92] and Peyrat [13, annexe 3.2]. For the sake of completeness, we give a slightly simpler proof. We will also give a more precise property pertaining to the shortest paths from vertices arrra (cf. Proposition 3.2 below). Lemma 3.1. If a path of the form LRL * is a shortest path, where l ú 0, r ú 0, l * ú 0, then l / l * ° r. Similarly, if a path of the form RLR * is a shortest path, where r ú 0, l ú 0, r * ú 0, then r / r * ° l. Proof. We consider the shortest paths of the form LRL *. The case of RLR * is analogous. We first prove that l õ r and l * õ r. Given a path of the form LRL * from X Å x1rrrxD to Y, suppose that l ¢ r; then after the application of L to X, we reach vertex xl/1rrrxDb1rrrbl . The application of R leads to the vertex arrrra1 xl/1rrrxDb1rrrbl0r . The first shift of L * leads to the vertex ar01rrra1 xl/1rrrxDb1rrrbl0rb. But the vertex ar 01rrra1 xl/1rrrxDb1rrrbl0rb could have been reached by a shorter path L1 R1 with l1 Å l and r1 Å r 0 1 (L1 introduces the word b1rrrbl0rbrrrand R1 the word ar 01rrra1 ). Therefore, LRL * is not a shortest path. Thus, we have necessarily l õ r, and by symmetry (in considering the reverse path from Y to X, which is also a shortest path), l * õ r. Now, the vertices obtained by LRL * are of the form ar 0l =rrra1 xl/1rrrxD0 (r 0l ) b1rrrbl = , where a1rrrar 0l = and b1rrrbl = are arbitrary letters. These vertices can also be obtained via the sequence of shifts R1 L1 R2 with r1 Å r 0 l, l1 Å r, x1rrrxD r x2rrrxDb1 r x3rrrxDb1b2 r rrr r xl/1rrrxDb1rrrbl . / 8U16$$0780 08-19-97 19:15:05 r 2 Å r 0 l *. As LRL * is a shortest path, we have netwas W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS r1 / l1 / r2 Å 3r 0 l 0 l * ¢ l / r / l *, which implies that l / l * ° r. 193 At level k, 1 ° k ° D 0 1, we have three kinds of vertices: j Proposition 3.1. A shortest path of UB(d, D) is made of the concatenation of at most three directed paths, i.e., the shortest path is of the form LRL * or RLR *, where the cardinalities of these shift sequences can be zero. Proof. Suppose that a shortest path from X to Y is made of more than three directed paths, then a part of this shortest path is either L1 R1 L2 R2 or R1 L1 R2 L2 , with l1 ú 0, r1 ú 0, l2 ú 0, and r2 ú 0. Let us assume that it is the first case. It then follows that L1 R1 L2 R2 is a shortest path, and so are L1 R1 L2 and R1 L2 R2 . By Lemma 3.1, we j get l2 õ r1 and r1 õ l2 , which is a contradiction. (a) Those obtained with a directed path containing only left (respectively, right) shifts. Their number is at most 2Ak , with Ak Å d k , 1 ° k ° D 0 1. (11) (b) Those obtained with the concatenation of two directed paths corresponding to a sequence of LR (respectively, RL) shifts with l ú 0, r ú 0 and l / r Å k, where l Å É LÉ and r Å É RÉ. Consider the vertices obtained with a path LR. They are of the form H Proposition 3.2. A shortest path between a vertex X and the vertex arrra is of the form LR (with 0 ° r õ l) or RL (with 0 ° l õ r). Proof. Without loss of generality, suppose that the path between arrra and X is of the form LRL *. Suppose that l ° r, which is, in particular, the case if l * ú 0 by Lemma 3.1. The vertex reached after the operation LR is arrrra1arrra, which could have been reached directly by the path R which is shorter. j arrrra1 xl/1rrrxDb1rrr bl0r , if l ¢ r; arrrra1 xl/1rrrxD0 (r 0l ) if l õ r, where arrrra2 and b1rrrbl0r are arbitrary letters and a1 x xl . Indeed, if a1 Å xl , these vertices would have been reached with a path L1 R1 with l1 Å l 0 1 and r1 Å r 0 1 and so are already at level k 0 2. Thus, there are at most (d 0 1)d m0 1 vertices reached by such paths, where m Å max(l, r). Hence, for fixed k, 2 ° k ° D 0 1, the number of vertices reached by the concatenation of two directed paths is at most 2Bk , with 3.2. Lower Bound We now consider the lower bound of the mean eccentricity for general UB(d, D). k0 1 Bk Å ∑ (d 0 1)d max ( l , k0l ) 01 Proposition 3.3. For any D ¢ 2 and any X √ UB(d, D), 9 D 0 3 0 ú D 0 4.2, 8 eV (X ) ¢ lÅ1 k0 1 lÅ k / 2 d Å 2; 8 D 0 1 0 ú D 0 1.9, 9 d Å 3; 25 D010 ú D 0 1.4, 72 d Å 4; 0 (d 0 1)d k / 2 011 {k mod2Å0 } Å 2d 0 2d where x denotes the smallest integer greater than or equal to x, and 1 { l } is the indicator function. Therefore, Proof. Consider the shortest path tree rooted at X Å x1rrrxD . As in the case of directed de Bruijn networks, the more vertices that are at the first levels of the shortest path tree, the smaller is the mean eccentricity (cf. Lemma 2.1). We will use the fact that the shortest paths are made of the concatenation of at most three directed paths to obtain upper bounds of the widths of the first levels in the shortest path tree. 08-19-97 19:15:05 (12) k / 2 01 0 (d 0 1)d k / 2 011 {k mod2Å0 } , 2(d / 1) ¢ D 0 0.9, d ¢ 5. d(d 0 1) 2 / 8U16$$0780 k0 1 (10) 2 D0 ∑ d l0 1 ) Å 2(d 0 1)( Bk ° 2d k0 1 , 2 ° k ° D 0 1. (13) (c) Those obtained with the concatenation of three directed paths corresponding to a sequence of LRL * (respectively, RLR * ) shifts. Consider the path LRL *. We have l ú 0, r ú 0, l * ú 0, and l / r / l * Å k, where l Å É LÉ, r Å É RÉ and l * Å É L *É. According netwas W: Networks 780 194 BERMOND, LIU, AND SYSKA to Lemma 3.1, l / l * ° r, so that k ¢ 4. Consider the vertices obtained with a path LRL *. They are of the form lk (X ) ° 2Ak / 2Bk1 {k¢2 } / 2Ck1 {k¢4 } õ 2(d k / 2d k0 1 / d k0 2 ) Å mk , (17) 1 ° k ° D 0 1, ar 0l =rrra2a1 xl/1rrrxD0 (r 0l ) b1b2rrrbl = , where ar 0l =rrra2 and b2rrrbl = are arbitrary letters and a1 x xl , b1 x xD0 (r 0l ) /1 (otherwise, these vertices are already at a preceding level). Thus, there are at most (d 0 1) 2 d r 0 2 vertices reached by such paths. Hence, for fixed k, 4 ° k ° D 0 1, the number of vertices reached by the concatenation of three directed paths is at most 2Ck , with where lk (X ) is the width of level k in the shortest path trees rooted at vertex X. Let nd be the greatest integer n such that for all D¢2 n ∑ mk ° N 0 1. (18) kÅ1 Note that N Å d D and Ck Å k0 2 k0r 0 1 ∑ (d 0 1) 2 d r 0 2 . ∑ mk Å r Å k / 2 lÅ1 kÅ1 ∑ n Hence, it is readily checked that A simple calculation yields k0 2 D 0 4, d Å 2; ∑ (k 0 r 0 1)(d 0 1) 2 d r 0 2 Ck Å 2(d / 1) 2 n (d 0 1). d(d 0 1) nd ¢ r Å k / 2 D 0 2, d Å 3, 4; (19) k0 2 ∑ d r02 Å (k 0 1)(d 0 1) 2 D 0 1, d ¢ 5. r Å k / 2 (d 0 1) 2 d 0 Å (k 0 1)(d 0 1)(d 1 d F S k 2 0 0 k0 3 k0 2 ∑ rd r 0 1 r Å k / 2 0 d k / 2 02 ) (14) In fact, we have equality in (19) as soon as D ¢ 7 for d Å 2, D ¢ 4 for d Å 4, and any D ¢ 2 for other values of d. Applying now Lemma 2.1 implies that (k 0 2)d k0 1 0 (k 0 1)d k0 2 Å d k0 2 0 D 0 1 d k / 2 / k 2 k 2 n eV (X ) ¢ nd / 1 0 G d k / 2 01 Å nd / 1 0 d 1 ( ∑ (nd / 1 0 k)mk ) N 0 1 kÅ1 S d nd 0 1 2(d / 1) 2 (nd / 1) D d 01 d(d 0 1) d k / 2 01 / S k 2 0 D 0 1 d k / 2 02 , Å nd / 1 0 where x denotes the integer part of x. Hence, Ck ° d k0 2 . Therefore, (15) eV (X ) ¢ nd / 1 0 (16) 08-19-97 19:15:05 2(d / 1) 2 d nd/ 1 r . d(d 0 1) 2 d D (20) It is now a simple calculation from (19) and (20) to obtain relation (10). j It follows from relations (11), (13), and (15) that / 8U16$$0780 D 2(d / 1) 2 d nd/ 1 0 (nd / 1)d / nd r . dD 0 1 d(d 0 1) 2 For 1 ° k ° D 0 1, let mk Å 2(d k / 2d k0 1 / d k0 2 ) Å 2(d / 1) 2 d k0 2 . (nd / 1)d nd d nd/ 1 0 1 / d(d 0 1) d(d 0 1) 2 Observe that for small values of d and D closer lower netwas W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS bounds can be obtained using the exact values of Ak , Bk , and Ck [see (11), (12), and (14)] in mk Å 2Ak / 2Bk1 {k¢2 } / 2Ck1 {k¢4 } . Note also that for X Å arrra the lower bounds of Proposition 3.3 can be improved. Indeed, in that case, it follows from Proposition 3.2 that there exist only two kinds of vertices: type (a) with Ak Å d k and type (b) with Bk ° d k0 1 (as l ú r in the paths LR). Hence, we can do the computation with mk Å 2(d / 1)d k0 1 . This gives = 2(d / 1) d n d/ 1 eV (arrra) ¢ n *d / 1 0 r , (d 0 1) 2 d D (21) 195 putations for the case of small diameters. In Table I, we provide the numerical results of the mean eccentricities in the binary de Bruijn network UB(2, D). In particular, we present, for diameter D Å 2, 3, . . . , 18, the average (taken over all vertices) of the mean eccentricities, the maximal and the minimal weights of the shortest path trees, as well as the vertices which exhibit these weights. While the minimal weights are reached by different vertices, the maximal weights are obtained by the vertices 0rrr0 and 1rrr1 in all our experimentation. This leads us to the following conjecture: Conjecture. For any d ¢ 2 and D ¢ 2, the vertices arrra, where a is a letter of A, have the maximal mean eccentricity in UB(d, D). where D 0 3, d Å 2; n *d ¢ D 0 2, d Å 3; (22) D 0 1, d ¢ 4. As a simple corollary of Proposition 3.3, we obtain the asymptotic mean eccentricity when d goes to infinity. Corollary 3.1. For any D ¢ 2 and any X √ UB(d, D), lim eV (X ) Å D. dr` The above property shows that all the mean eccentricities are close to the diameter when the degree of the de Bruijn network is large. Therefore, in this case, we can simply use D shifts to route instead of the sophisticated optimal routing of the shortest path [12]. The global communication delay would even be decreased due to the simplicity of the routing algorithm. This conjecture is numerically verified for the binary de Bruijn network UB(2, D) with diameters up to 18. However, we were unable to prove it for the general case. Unlike the case of de Bruijn digraphs where we got closed form formulas for the mean eccentricities of some extremal vertices, in the undirected de Bruijn graphs, we were not even able to obtain a closed formula for the mean eccentricity of the probably simplest vertices arrra. Numerical computation (see Table II) indicates that the widths in the shortest path trees of UB(2, D) rooted at arrra are quite regular. It is possible to prove that for any 1 ° k ° D/2 the width at level k of the shortest path trees of UB(2, D), denoted lk (2, D), can be expressed as lk (2, D) 2 k / 2 k0 2 / 2 k0 3 /rrr / 2 2 p / 2 2 p0 2 Å 2 k / 2 k0 1 0 2 2 p / 2 2 p0 2 , Å 3.3. Upper Bound 1 D / . d01 N01 (23) This bound is not tight. In the remainder of the paper, we will study upper bounds in more detail. To obtain some intuition, we start with numerical com- / 8U16$$0780 2 /2 k0 2 /2 k0 3 k Å 3p; /rrr / 2 2 p Å 2 k / 2 k0 1 0 2 2 p , It is clear that the mean eccentricity of any vertex X in the undirected de Bruijn network UB(d, D) is smaller than the mean eccentricity of the same vertex in the directed de Bruijn network B(d, D). Therefore, Proposition 2.2 still holds for undirected de Bruijn network UB(d, D), i.e., for any d ¢ 2 and D ¢ 2 and for all X √ UB(d, D), eV (X ) ° D 0 k 08-19-97 19:15:05 k Å 3p / 1; 2 k / 2 k0 2 / 2 k0 3 /rrr / 2 2 p/ 1 Å 2 k / 2 k0 1 0 2 2 p/ 1 , k Å 3p / 2. Unfortunately, it is nontrivial to characterize lk (2, D) for k ú D/2. These numbers are not so regular as to yield simple recursive equations. It seems that for any fixed diameter the widths are unimodal with the maximum at D 0 1. It also seems that lD/10k (2, D / 1) ° 2lD0k (2, D) for k Å 0, 1, 2, and lD/10k (2, D / 1) ¢ 2lD0k (2, D) for k ¢ 3. In what follows, we will first consider the asymptotic value of eV (arrra) when D tends to infinity. More precisely, we will prove that the limit of netwas W: Networks 780 196 BERMOND, LIU, AND SYSKA TABLE I. Mean eccentricities of UB(2, D) D Maximum eV (X) vertex arrra Average eV (X) Minimum eV (X) Vertices 2 1.1667 1.3333 1.0000 01 10 3 1.6429 2.0000 1.4286 4 2.1417 2.6667 1.8667 001, 011 110, 100 0011 1100 5 2.7540 3.4516 2.5484 00011, 00111 11100, 11000 6 3.4534 4.2698 3.2063 001011 110100 7 4.2148 5.1654 3.9685 0001011, 0010111 1110100, 1101000 8 5.0280 6.0706 4.08078 00010111 11101000 9 5.8844 7.0098 5.6888 001111010, 010111100 110000101, 101000011 10 6.7737 7.9589 6.5689 0010111100, 0011110100 1101000011, 1100001011 11 7.6886 8.9253 7.4934 00101111100, 00111110100 11010000011, 11000001011 12 8.6232 9.8960 8.4308 001101011100, 001110101100 110010100011, 110001010011 13 9.5733 10.8764 9.3770 0011010111100, 0011110101100 1100101000011, 1100001010011 14 10.5351 11.8594 10.3377 00101111110100 11010000001011 15 11.5063 12.8473 11.3107 001011111101100, 001101111110100 110100000010011, 110010000001011 16 12.4844 13.8372 12.2936 0010111111101100, 0011011111110100 1101000000010011, 1100100000001011 17 13.4678 14.8297 13.2790 00101101111110100, 00101111110110100 11010010000001011, 11010000001001011 18 14.4554 15.8233 14.2669 001011111010100011, 001110101000001011 110100000101011100, 110001010111110100 def D(X ) Å D 0 eV (X ) exists when X Å arrra, and we will provide a numerical recursive scheme for its computation. We will also establish an upper bound [better than (23)] for arbitrary X. As a consequence of these two results, we show that for any fixed degree (2d) the asymptotic difference between eV ( X ) and eV (arrra) when the diameter goes to infinity is smaller than 0.22. / 8U16$$0780 08-19-97 19:15:05 Let X √ UB(d, D) and 0 ° h ° D. Define Eh (X ) to be the set of vertices that are at distance no greater than D 0 h from X: Eh (X ) Å {Y É d(X, Y ) ° D 0 h}. By definition, E0 (X ) contains all the vertices of UB(d, D) and ED (X ) is a singleton. Let eh (X ) Å É Eh (X )É/N be the proportion of vertices that are at distance no netwas W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS 197 TABLE II. Widths in the shortest path trees of UB(2, D) rooted at arrra lk(2, D) k UB(2, 18) UB(2, 19) UB(2, 20) UB(2, 21) UB(2, 22) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2 4 9 20 40 84 176 352 720 1469 2926 5865 11648 22444 41559 68474 79558 26793 2 4 9 20 40 84 176 352 720 1471 2936 5911 11846 23268 45081 83382 136638 158954 53393 2 4 9 20 40 84 176 352 720 1472 2941 5934 11945 23680 46764 90549 166578 273450 317504 106351 2 4 9 20 40 84 176 352 720 1472 2943 5944 11991 23878 47588 93976 180959 333665 547235 633746 212347 2 4 9 20 40 84 176 352 720 1472 2944 5949 12014 23977 48000 95660 187888 362679 668397 1093347 1266714 423855 greater than D 0 h from X. Then, e0 (X ) Å 1 and eD (X ) Å 1/N. Lemma 3.2. For any d ¢ 2, D ¢ 2, and any X √ UB(d, D), Ph ,k Å {X É X Å UAV, A Å arrra, D0 1 D01 N eV (X ) Å D / 0 ∑ eh (X ). N 0 1 N 0 1 hÅ1 We will first consider the vertices arrra. For simplicity of notation, we arbitrarily fix a letter a √ A and denote Eh å Eh (arrra), and eh å eh (arrra). Let (24) Proof. For any 0 ° h ° D 0 1, the set of vertices that are exactly at distance D 0 h from X is Eh (X ) 0 Eh/1 (X ). Since Eh/1 (X ) ⊆ Eh (X ), we obtain that the number of vertices that are at distance D 0 h from X is Neh (X ) 0 Neh/1 (X ). Therefore, É AÉ Å k / h, ÉUÉ Å k}, Sh ,k Å {X É X Å UAV, A Å arrra, É AÉ Å k / h, ÉV É Å k}. Lemma 3.3. For any 0 ° h ° D, Eh Å D0 1 1 eV (X ) Å ∑ (D 0 h)N(eh (X ) 0 eh/1 (X )) N 0 1 hÅ0 N N01 S 0 e2 (X ) 0rrr0 eD (X )) D0 1 D0 1 0 ∑ eh (X ) N hÅ1 D D0 1 Å D/ D01 N 0 ∑ eh (X ). N 0 1 N 0 1 hÅ1 / 8U16$$0780 08-19-97 19:15:05 Eh ,k , where Eh ,k Å Ph ,k < Sh ,k . N Å (De0 (X ) 0 e1 (X ) N01 Å < 0°k° ( D0h ) / 2 j Proof. Let X be a vertex in Ph ,k , where 0 ° k ° (D 0 h)/2. Then, X Å UAV, with A Å arrra, É AÉ Å k / h and ÉUÉ Å k. Thus, X can be reached from arrra by first D 0 (k / h) left shifts applied to arrra introducing the suffix V V *, where V * is an arbitrary word with length k, and then k right shifts introducing prefix U. The length of the corresponding path is D 0 (k / h) / k Å D 0 h. Hence, X √ Eh . Similarly, we can show that if X √ Sh ,k , then X √ Eh . Therefore, netwas W: Networks 780 198 BERMOND, LIU, AND SYSKA Eh fl < 0°k° ( D0h ) / 2 Eh ,k . (25) ( D0h ) / 2 eh Å ( D0h ) / 2 ∑ ∑ eh ,k ° kÅ0 Suppose now that X is a vertex in Eh . Then, by Proposition 3.2, there exists a path (not necessarily a shortest one) between arrra and X of the type LR or RL with r / l ° D 0 h, where r Å É RÉ, l Å É LÉ. Without loss of generality, suppose that this path is of the form LR. Thus, X can be written as X Å UAV, with U Å arrrra1 , A Å arrra, V Å b1rrrbl0r , where l ¢ r (cf. Proposition 3.2, where the equality holds when l Å r Å 0). It then follows that < Eh ,k . D0 1 p q hÅ1 hÅ1 kÅ0 p hÅ1 kÅq/1 p ( D0h ) / 2 hÅ1 kÅq/1 q ∑ ∑ eh ,k / ∑ ° j Å0 . N hÅ1 kÅ0 p Å (∑ ( D0h ) / 2 ∑ eh ,k ) / 2 F G On the other hand, it is easy to see that D0 1 ∑ eh ¢ ∑ D0 1 ( D0h ) / 2 ∑ hÅ1 hÅ1 kÅ0 p q eh ,k ¢ ∑ ∑ eh ,k; hÅ1 kÅ0 j ` ∑ eh ,k . (28) ` lim D(arrra) Å ∑ ∑ eh ,k ° hÅ1 kÅ0 2d . (32) (d 0 1) 2 Proof. Let p Å q Å D/3 in (29), and let D go to 1 ` readily implies that the limit of ( D0 hÅ1 eh exists when D r ` and that ` ` lim ∑ eh Å ∑ ∑ eh ,k . Lemma 3.4. For any fixed d ¢ 2 and any p, q ° D/ 3, Dr` hÅ1 hÅ1 kÅ0 Applying Lemma 3.2 entails that D0 1 ∑ ∑ eh ,k ° ∑ eh ` hÅ1 q ∑ eh ,k ) / 2 hÅ1 kÅ0 S d 0q / d 10 p (d 0 1) 2 D (29) Dr` hÅ1 kÅ0 . Using again inequality (30) yields ` ` ` ` ∑ ∑ eh ,k ° 2 ∑ ∑ d 0h0k Å É Ph ,kÉ Å 2d 0h0k , N hÅ1 kÅ0 (30) 0 ° k, h ° D, hÅ1 kÅ0 The proof is thus completed. 2d . (d 0 1) 2 j 2k / h ° D, A recursive scheme will be provided after for the computation of limDr` D(arrra). The convergence of the which implies that / 8U16$$0780 ` lim D(arrra) Å ∑ ∑ eh ,k . Proof. Note first that eh ,k ° 2 2d 10 h hÅp/1 d 0 1 d 0q / d 10 p . (d 0 1) 2 D0 1 p ` hÅ1 kÅq/1 q kÅ0 ° (∑ 2d 10 h hÅp/1 d 0 1 ` hÅ1 kÅ0 (27) It then follows that hÅ1 kÅ0 D0 1 2d 0h0k / ∑ ∑ ∑ eh ,k / ∑ ∑ 2d 0h0k / ∑ ° Dr` q hÅp/1 Proposition 3.4. For any fixed d ¢ 2, k0 1 p eh ,k / ∑ eh ∑ ` q D0 1 ∑ hence, the result. É Eh ,k 0 < Eh ,jÉ eh Å ( D0h ) / 2 p ∑ eh Å ∑ ∑ eh ,k / ∑ p For h ¢ 1 and k ¢ 0, let (31) Thus, for any p, q ° D/3 , Combining relations (25) and (26) readily implies the assertion of the lemma. j eh ,k Å 2d 10 h Å . d01 0h0k kÅ0 hÅ1 kÅ0 (26) ∑ 2d ° Let A * be the prefix of A with size r / h. Then, X can be written as X Å UA *V * so that X √ Ph ,r . Since ÉV *É Å D 0 r 0 (r / h) ¢ ÉV É ¢ 0, we get that r ° (D 0 h)/2. Therefore, 0°k° ( D0h ) / 2 kÅ0 ` É AÉ Å D 0 r 0 (l 0 r) ¢ D 0 (D 0 h) / r Å r / h. Eh ⊆ 2d 0h0k 08-19-97 19:15:05 netwas W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS series ( `hÅ1 ( `kÅ0 eh ,k is very fast. Good precisions are obtained with computations stopped at quite small indices h, k. Indeed, Lemma 3.4 and Proposition 3.4 imply that for any n ¢ 1 n n ∑ ∑ eh ,k ° lim D(arrra) hÅ1 kÅ0 x1rrrxk/1 Ak/1/hV, where x1 , . . . , xk/1 are arbitrary letters, Ai is a word of length i with letter a, and V is an arbitrary word. The words in Ph ,k are of the form x1rrrxk Ak/hV *. Therefore, the words in Ph ,k/1 0 Ph ,k are of the form x1rrrxkaV Ak/1/hV, where aV is an arbitrary letter in A 0 {a}. Thus, hh ,k Å d 0 ( k/h/ 1 ) (d 0 1)/d. j Dr` n n 2(d / 1) 0n õ ( ∑ ∑ eh ,k ) / d . (d 0 1) 2 hÅ1 kÅ0 (33) Lemma 3.6. For all h ¢ 1 and k ¢ 0 such that 2k / 2 / h ° D, gh ,k/1 Å gh ,k / dh ,k . In view of the above results, we see that the computation of limit of D(arrra) can be carried out on the values of eh ,k for small h and k. We derive below a recursive computational scheme for eh ,k . This will be based on counting the proportion of words (of length D over the alphabet A ) fulfilling some conditions. This approach and some of the ideas can be found in [1]. Let C be a condition on the words of length D over A. Let CV be the opposite condition of C. Two conditions, C1 and C2 , are said to be independent if they concern disjoint subgroups of letters of the word. Let p(C) denote the proportion of words satisfying a condition C. We recall the following basic computation rules which will be used in the remainder of the paper: • The proportion of words satisfying CV is 1 0 p(C), i.e., p(CV ) Å 1 0 p(C). • If C1 and C2 are independent, then the proportion of words satisfying both C1 and C2 is p(C1 )p(C2 ), i.e., p(C1 , C2 ) Å p(C1 )p(C2 ). For h ¢ 1 and k ¢ 0, let hh ,k Å j Å0 N j Å0 k j Å0 N k j Å0 j Å0 j Å0 k É Sh ,k/1 0 < Sh ,jÉ å j Å0 N . For k Å 01, hh ,01 Å dh ,01 Å É Ph ,0É/N Å d 0h . For k ° 01, gh ,k Å 0. It is also clear that gh ,0 Å d 0h . Lemma 3.5. For all h ¢ 1 and k ¢ 0 such that 2k / 2 / h ° D, hh ,k Å (d 0 1)d 0 ( k/h/ 2 ) . dh ,k Å (1 0 gh , ( k0h ) / 2 ) hh ,k , k ¢ 01; (36) Å (1 0 gh , ( k0h ) / 2 )(d 0 1)d 0 ( k/h/ 2 ) , k ¢ 0. (37) Proof. As seen in the proof of Lemma 3.5, the words in Ph ,k/1 0 Ph ,k are of the form x1rrrxkaV Ak/1/hV, where aV is an arbitrary letter in A 0 {a}. It then follows that these words will not appear in Ph ,j for all j such that j õ k and 2 j / h ú k. Therefore, k Ph ,k/1 0 Ph ,k Å Ph ,k/1 0 < j Å ( k0h ) / 2 /1 k ( k0h ) / 2 j Å0 j Å0 Ph ,j , (38) Ph ,j . (39) (34) 08-19-97 19:15:05 < It is easily verified that the conditions for words to be in ( k0h ) / 2 Ph ,j are independent (the Ph ,k/1 0 Ph ,k and in < j Å0 former is on xk/1rrrx2k/2/h of word X Å x1rrrxD , whereas the latter is on x1rrrxk ). Therefore, relation (39) implies relation (36) according to the basic computation rule. Relation (37) follows from those of (34) and (36). j Proposition 3.5. For all h ¢ 1 and k ¢ 0 such that 2k / h ° D/2, eh ,k Å (2 0 gh ,k01 0 gh ,k ) dh ,k01 , k ¢ 0; (40) eh ,k Å (2 0 gh ,k01 0 gh ,k )(1 0 gh , ( k0h01 ) / 2 ) 1 (d 0 1)d 0 ( k/h/ 1 ) , Proof. The words in Ph ,k/1 are of the form / 8U16$$0780 j Lemma 3.7. For all h ¢ 1 and k ¢ 01 such that 2k / 2 / h ° D, Ph ,k/1 0 < Ph ,j Å Ph ,k/1 0 Ph ,k 0 , N É Ph ,k/1 0 < Ph ,jÉ dh ,k Å k which, in turn, implies that É < Sh ,jÉ å k/ 1 É < Ph ,jÉ Å É < Ph ,jÉ / É Ph ,k/1 0 < Ph ,jÉ. k É < Ph ,jÉ (35) Proof. The assertion comes from the fact that É Ph ,k/1 0 Ph ,kÉ É Sh ,k/1 0 Sh ,kÉ å , N N k gh ,k Å 199 netwas W: Networks 780 k ¢ 1. (41) 200 BERMOND, LIU, AND SYSKA TABLE III. D(arrra) in UB(2, D) kÅ0 eh,k kÅ1 kÅ2 kÅ3 kÅ4 kÅ5 (5kÅ1 eh,k hÅ1 0.75000 0.10938 0.02246 0.01050 0.00381 0.00188 0.89802 hÅ2 0.43750 0.08984 0.04110 0.01524 0.00752 0.00342 0.59552 hÅ3 0.23438 0.05371 0.02612 0.01288 0.00560 0.00279 0.33547 hÅ4 0.12109 0.029053 0.01434 0.00713 0.00355 0.00166 0.17683 hÅ5 0.06152 0.01508 0.00750 0.00373 0.00186 0.00093 0.09062 hÅ6 0.03101 0.00768 0.00383 0.00191 0.00095 0.00048 0.04585 ( 1.63550 0.30473 0.11624 0.05140 0.02330 0.01116 2.14232 1.66667 0.31250 0.11914 0.05235 0.02388 0.01146 2.18600 6 kÅ1 eh,k êk Under the assumption that 2k / h ° D/2, the conditions 1 k0 1 for words to be in Ph ,k 0 < k0 j Å0 Ph ,j and in < j Å0 Sh ,j are independent (the former is on the left-half part of the word, whereas the latter is on the right-half part of the word). Therefore, Proof. k0 1 É Ph ,k < Sh ,k 0 < Eh ,jÉ j Å0 eh ,k Å N k0 1 k0 1 É Ph ,k 0 < Eh ,jÉ Å j Å0 j Å0 N k0 1 k0 1 j Å0 j Å0 j Å0 Similarly, N k0 1 k É Sh ,k 0 < Sh ,j 0 < Ph ,jÉ j Å0 j Å0 N N j Å0 . h eh (hiÅ1 ei 1 2 3 4 5 6 7 8 9 10 11 12 13 : 30 : 60 0.8997111342 0.5988445366 0.3381424180 0.1784738644 0.0915215694 0.0463216922 0.0232996659 0.0116843542 0.0058507839 0.0029275407 0.0014643071 0.0007322877 0.0003661774 0.899711134 1.498555671 1.836698089 2.015171953 2.106693523 2.153015215 2.176314881 2.187999235 2.193850019 2.196777560 2.198241867 2.198974155 2.199340332 : 2.199706529 : 2.199706532 017 0.260 1 10 j Å0 Å dh ,k01 (1 0 gh ,k ). Hence, relation (40) holds. Relation (41) follows from j (36) and (40). TABLE IV. D(arrra) in UB(2, D) 0.0000000027 k k0 1 É Sh ,k 0 < Sh ,j 0 < Ph ,jÉ / Å dh ,k01 (1 0 gh ,k01 ). N É Ph ,k 0 < Ph ,j 0 < Sh ,jÉ Å k0 1 É Ph ,k 0 < Ph ,j 0 < Sh ,jÉ j Å0 / N k0 1 É Sh ,k 0 Ph ,k 0 < Eh ,jÉ Lemmas 3.5, 3.6, and 3.7 and Proposition 3.5 enable us to compute recursively eh ,k . In Table III, we indicate the values of eh ,k in the case d Å 2 for 1 ° h ° 6 and 0 ° k ° 5. This gives already a lower bound of 2.14 for D(arrra). In fact, we have computed all the eh ,k for d Å 2, h ° 30 and k ° 85. Results for eh are given in Table IV. The values are given with 10 digits but we have computed them with infinity precision. Recall that by having the values of eh we obtain the number of vertices at distance exactly D 0 h. For instance, we have 1 0 e1 á 10.03% of vertices at distance D from (arrra) in the case d Å 2. This table shows that most of the vertices are at distance D 0 h with h small. Finally, let us note that one can get closed form formulas for êk where ` eP k Å ∑ eh ,k . hÅ1 / 8U16$$0780 08-19-97 19:15:05 netwas W: Networks 780 (42) MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS We give below this formulas for 0 ° k ° 6: eP 0 Å 2d / 1 d2 0 1 eP 1 Å 2d 2 0 2d / 1 d4 6 eP 2 Å 5 We now turn back to upper bounds for arbitrary vertex X. Let us consider an arbitrarily fixed vertex X Å x1rrrxD . Let Ph ,k (X ) Å {Z ÉZ Å UXh ,kV, Xh ,k Å xD0h0k/1 xD0h0k/2rrrxD , ÉUÉ Å k}, 4 3 2 2d 0 4d / 4d / d 0 3d / 1 d9 Sh ,k (X ) Å {Z ÉZ Å UX eP 4 Å d 022 (2d 17 0 4d 16 / 2d 15 / 4d 14 0 4d 13 / d 12 0 2d 0d 9 7 6 / 7d 0 6d 0 d / 5d Lemma 3.8. For any 0 ° h ° D, eP 5 Å d 028 (2d 22 0 4d 21 / 2d 20 / 4d 19 0 6d 18 / 4d 17 / d 16 0 6d 15 / d 14 / 8d 13 0 2d 12 0 10d 11 / 11d 10 0 2d 9 0 3d 8 0 d 6 / 2d 5 0 d 2 / 2d 0 1) eP 6 Å d ( 01 / 2d / 8d 4 5 10 2 0 d / 2d 6 0 2d / 6d 0 3d / 5d 18 24 s h ,k 5 Eh (X ) fl 0 4d 4 / 2d 3 0 d 2 / 2d 0 1) 034 V, X Eh ,k (X ) Å Ph ,k (X ) < Sh ,k (X ). 0 3d 6 / 2d 5 0 d 4 0 2d 3 / d 2 / 2d 0 1) 10 s h ,k Å x1 x2rrrxh/k , ÉV É Å k}, eP 3 Å d 016 (2d 12 0 4d 11 / 4d 10 0 2d 9 / d 8 / 2d 7 11 201 / 3d < 0°k° ( D0h ) / 2 Eh ,k (X ). Proof. The proof is analogous to the first part of the proof of Lemma 3.3 and is thus omitted. j Proposition 3.7. For any fixed d ¢ 2 and D ¢ 2, 20 D0 1 ∑ eh (X ) ú u(d) 0 22d 0D / 4 , 8 / d 0 2d 7 0 3d 12 (44) hÅ1 0 2d 9 0 2d 16 0 8d 11 0 2d 15 0 2d 14 / 8d 13 0 4d 19 / 2d 17 0 4d 21 / 2d 25 0 4d 26 / 2d 27 ). In Table III, we also provided exact values of êk for d Å 2. Again, we note that using only ( 6kÅ0 êk gives a very good estimation of D(arrra). Indeed, it follows from Lemma 3.4 and Proposition 3.4 that for any q ¢ 0 where u(d) Å 2d / 1 2d 0 1 1 / 3 0 d2 0 1 d 0 (d 0 1) 2 d 3 / 1 2d 6 0 d 5 / 2d 4 0 d 3 / d 2 / d 0 1 Å 7 . d 0 2d 6 / 3d 5 0 2d 4 0 d 3 / 3d 2 0 3d / 1 (45) (43) Proof. The proof is technical and involved so that we omit it here. The interested reader can find the detailed proof in the technical report [4]. j The following proposition gives values of limD r` D(arrra) for d ° 7. There, again, we give only truncated values with five decimals. The values given in parentheses are approximation using ( 6kÅ0 êk . As a corollary of Lemma 3.2 and Proposition 3.7, we obtain q q ∑ eP k ° lim D(arrra) õ ( ∑ eP k ) / kÅ0 Dr` kÅ0 2d 0q . (d 0 1) 2 Proposition 3.6. In the de Bruijn network UB(d, D), 2.19970 d Å 2 (2.19151) 1.09605 d Å 3 (1.09556) lim D(arrra) Å Dr` 0.72359 d Å 4 (0.72353) 0.53752 d Å 5 (0.53751) 0.42652 d Å 6 (0.42652) Corollary 3.2. For any d ¢ 2, D ¢ 2, and any X √ UB(d, D), eV (X ) õ D 0 u(d) / 22d 0D / 4 1 / r(D 0 1 0 u(d) / 22d 0D / 4 ), N01 where u( d) is defined in (45). 0.35304 d Å 7 (0.35303). / 8U16$$0780 08-19-97 19:15:05 Proof. It follows from (24) and (44) that netwas W: Networks 780 (46) 202 BERMOND, LIU, AND SYSKA D0 1 eV (X ) Å D 0 ∑ eh (X ) hÅ1 D0 1 / 1 r(D 0 1 0 ∑ eh (X )) N01 hÅ1 õ D 0 u(d) / 22d 0D / 4 1 r(D 0 1 0 u(d) / 22d 0D / 4 ). N01 / j As a consequence of Proposition 3.4 and the above corollary, we obtain Proposition 3.8. For any fixed d ¢ 2, ` ` lim sup (eV (X ) 0 eV (arrra)) õ ( ∑ ∑ eh ,k ) 0 u(d), Dr` hÅ1 kÅ0 where u( d) is defined in (45). Proof. It follows from Proposition 3.4 that lim sup (eV (X ) 0 eV (arrra)) We thank the anonymous referees for their helpful remarks. M. S. was supported by INRIA while visiting the Simon Fraser University, BC, Canada. Dr` Å lim D(arrra) 0 lim inf D(X ) Dr` ` ¢ (∑ bounds as well as the extremal vertices which reach these bounds. For the undirected de Bruijn network, we have provided lower and upper bounds which differ from the diameter by some small constants. We conjecture that the vertices of the form arrra have the largest mean eccentricity. This conjecture has been verified by numerical computations for binary de Bruijn networks with diameters up to 18. We have shown that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of arrra is a small constant tending to zero with the degree. We have also provided a simple recursive scheme for the computation of the asymptotic mean eccentricity of the vertices arrra. We have proved that in both directed and undirected de Bruijn networks all the mean eccentricities tend to the diameter when the degree goes to infinity. This implies that when the degree is large, the simple routing algorithm which consists of doing left shifts all the time or right shifts all the time is more efficient than are optimal routing algorithms. In general, the gain of applying optimal routing algorithms is quite limited, even without considering their overheads. Dr` ` ∑ eh ,k ) 0 u(d), hÅ1 kÅ0 REFERENCES where the inequality comes from (46). j [1] Numerical results for small d are given below: [2] Proposition 3.9. 0.2155 d Å 2 [3] 0.0393 d Å 3 lim sup (eV (X ) 0 eV (arrra)) õ Dr` 0.0117 d Å 4 [4] 0.0045 d Å 5 0.0021 d Å 6 0.0011 d Å 7. [5] 4. CONCLUSIONS [6] In this paper, we have provided upper and lower bounds of the mean eccentricities of the de Bruijn networks. For the directed de Bruijn network, we have presented tight [7] / 8U16$$0780 08-19-97 19:15:05 netwas J.-C. Bermond, J. Bond, W. Fernandez de la Vega, S. Rudich, and M. Santha, The radius of graphs on alphabets. Graph Combin. (1988), preprint. J.-C. Bermond, C. Delorme, and J.-J. Quisquater, Strategies for interconnection networks: Some methods from graph theory. JPDC 3 (1986) 433–449. J.-C. Bermond, N. Homobono, and C. Peyrat, Large fault-tolerant interconnection networks. Graph Combin. 5 (1989) 107–123. J.-C. Bermond, Z. Liu, and M. Syska, Mean eccentricities of de Bruijn networks. Rapport de recherche INRIA, No. 2114, 1993. Research Report of I3S, Université de Nice Sophia Antipolis, No. 94-02 (1994). J.-C. Bermond and C. Peyrat, De Bruijn and Kautz networks: A competitor for the hypercube? Hypercube and Distributed Computers (J. P. Verjus and F. André, Eds. North-Holland (1989) 279–294. I. Bond, Constructions de grands réseaux d’interconnexion. PhD Thesis, Université de Paris-Sud, Centre d’Orsay (1984). F. Buckley and F. Harary, Distance in Graphs. AddisonWesley, Redwood City, CA (1990). W: Networks 780 MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS [8] N. G. de Bruijn, A combinatorial problem. Koninklijke Nederlands Akademie van Wetenschappen Proceedings 49-2 (1946) 758–764. [9] M. A. Fiol, J. L. A. Yebra, and I. Alegre de Miquel, Line digraph iterations and the (d, k) digraph problem. IEEE Trans. Comput. C-33(5) (1984) 400–403. [10] S. W. Golomb, Shift Register Sequences. Holden-Day, San Francisco, CA (1967). [11] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA (1992). / 8U16$$0780 08-19-97 19:15:05 [12] 203 Z. Liu, Optimal routing in the De Bruijn networks. Proceedings of the Tenth International Conference on Distributed Computing Systems, Paris, France (May 1990) 537–544. [13] C. Peyrat, Vulnérabilité dans les grand réseaux d’interconnexion. PhD thesis, Université de Paris-Sud, Centre d’Orsay (1984). [14] M. R. Samatham and D. K. Pradhan, The de Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI. IEEE Trans. Comput. 38(4) (1989) 567–581. netwas W: Networks 780

1/--страниц