Non-hyperbolicity in random regular graphs and their traffic characteristics

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n log _d?1 ³ n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.