MEAN ECCENTRICITIES OF DE-BRUIJN NETWORKS

Given a graph G = (V, E), we define (e) over bar(X), the mean eccentri city of a vertex X, as the average distance from X to all the other ve rtices of the graph. The computation of this parameter appears to be n ontrivial in the case of the de Bruijn networks. In this paper, we con sider upper and lower bounds for (e) over bar(X). For the directed de Bruijn network, we provide tight bounds as well as the extremal vertic es which reach these bounds. These bounds are expressed as the diamete r minus some constants. In the case of undirected networks, the comput ation turns out to be more difficult. We provide lower and upper bound s which differ from the diameter by some small constants. We conjectur e that the vertices of the form a. . . a have the largest mean eccentr icity. Numerical computations indicate that the conjecture holds for b inary de Bruijn networks with diameters up to 18. We also provide a si mple recursive scheme for the computation of the asymptotic mean eccen tricity of the vertices a . . . a. Finally, we prove that the asymptot ic difference, when the diameter goes to infinity, between the mean ec centricities of an arbitrary Vertex and that of a . . . a is smaller t han a small constant tending to zero with the degree. A byproduct of o ur 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) te nd to the diameter when the degree goes to infinity. (C) 1997 John Wil ey & Sons, Inc.