Non-hyperbolicity in random regular graphs and their traffic characteristics

作者：Tucci Gabriel H^*

来源：Central European Journal of Mathematics, 2013, 11(9): 1593-1597.

DOI：10.2478/s11533-013-0268-y

• Random regular graph
• Hyperbolic spaces
• Traffic flow

In this paper we prove that random d-regular graphs with d a parts per thousand yen 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 -> a.

• 出版日期2013-9