Traffic Congestion in Expanders, $(p,\delta )$--Hyperbolic Spaces and Product of Trees

Abstract

In this paper we define the notion of $(p,\delta )$--Gromov hyperbolic space where we relax Gromov's {\it slimness} condition to allow that not all but a positive fraction of all triangles are $\delta$--slim. Furthermore, we study maximum vertex congestion under geodesic routing and show that it scales as $\Omega (p^2{n}^2/D_n^2)$ where $D_n$ is the diameter of the graph. We also construct a constant degree family of expanders with congestion $\Theta (n^2)$ in contrast with random regular graphs that have congestion $O(n{\log }^3(n))$. Finally, we study traffic congestion on graphs defined as product of trees.

12 pages, 1 figure

References in corpus (1)

• Curvature and temperature of complex networks

Cited by in corpus (1)

• Expanders are order diameter non-hyperbolic