HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Mean eccentricities of de Bruijn networks

Abstract : Given a graph $G = (V, E)$, we define $\bar{e}(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 e(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 a· · ·a 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 a· · ·a. Finally, we prove that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of a· · ·a 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.
Complete list of metadata

https://hal.inria.fr/hal-03220046
Contributor : Jean-Claude Bermond Connect in order to contact the contributor
Submitted on : Thursday, May 6, 2021 - 10:29:32 PM
Last modification on : Friday, February 4, 2022 - 3:08:52 AM
Long-term archiving on: : Saturday, August 7, 2021 - 7:48:19 PM

File

100-BLS7-meaneccenctrictiesdeb...
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Claude Bermond, Zhen Liu, Michel Syska. Mean eccentricities of de Bruijn networks. Networks, Wiley, 1997, 30 (3), pp.187-203. ⟨10.1002/(SICI)1097-0037(199710)30:3<187::AID-NET4>3.0.CO;2-H⟩. ⟨hal-03220046⟩

Share

Metrics

Record views

16

Files downloads

18