On the hyperbolicity of random graphs

2014/01/22 by Dieter Mitche, Mitche, Dieter, Paweł Prałat +1
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1401.5678

Abstract

Let G=(V,E) be a connected graph with the usual (graph) distance metric d:V × V → N ∪ \0 \. Introduced by Gromov, G is δ-hyperbolic if for every four vertices u,v,x,y ∈ V, the two largest values of the three sums d(u,v)+d(x,y), d(u,x)+d(v,y), d(u,y)+d(v,x) differ by at most 2δ. In this paper, we determinate the value of this hyperbolicity for most binomial random graphs.

Related

• Random Regular Graphs are not Asymptotically Gromov Hyperbolic
• On the Hyperbolicity of Small-World and Tree-Like Random Graphs
• Hyperbolicity, slimness, and minsize, on average
• A bound for the diameter of random hyperbolic graphs
• Characterizing Hyperbolicity in Graphs