Random Regular Graphs are not Asymptotically Gromov Hyperbolic

Abstract

In this paper we prove that random $d$--regular graphs with $d\ge 3$ have traffic congestion of the order $O(n{\log }_{d-1}^3(n))$ where $n$ is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically $\delta$--hyperbolic for any non--negative $\delta$ almost surely as $n\to \infty$.

6 pages, 2 figures

References in corpus (1)

• Hyperbolic Geometry of Complex Networks