On the hyperbolicity of random graphs

zbMATH Open1300.05286arXiv1401.5678MaRDI QIDQ405243FDOQ405243

Authors: D. Mitsche, Paweł Prałat 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $G=(V,E)$ be a connected graph with the usual (graph) distance metric $d:VimesVoNcup0$. Introduced by Gromov, $G$ is $delta$-hyperbolic if for every four vertices $u,v,x,yinV$, 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 $2delta$. In this paper, we determinate the value of this hyperbolicity for most binomial random graphs.

Full work available at URL: https://arxiv.org/abs/1401.5678

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the diameter of hyperbolic random graphs
• On the diameter of hyperbolic random graphs
• scientific article; zbMATH DE number 6303023
• On the structure of random hypergraphs
• The modularity of random graphs on the hyperbolic plane
• Non-hyperbolicity of random graphs with given expected degrees
• A Bound for the Diameter of Random Hyperbolic Graphs
• Hyperbolicity, degeneracy, and expansion of random intersection graphs

zbMATH Keywords

diameterhyperbolicityrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• Title not available (Why is that?)
• Distance-hereditary graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Expanders are not hyperbolic
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Finite Transitive Graph Embeddings into a Hyperbolic Metric Space Must Stretch or Squeeze
• Recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs
• 1-Hyperbolic Graphs
• Geodesics and almost geodesic cycles in random regular graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Gromov hyperbolicity and cop and robber game

Cited In (13)

• A Bound for the Diameter of Random Hyperbolic Graphs
• When can graph hyperbolicity be computed in linear time?
• Mathematical properties on the hyperbolicity of interval graphs
• Generating Random Hyperbolic Graphs in Subquadratic Time
• On the hyperbolicity constant in graphs
• Cliques in hyperbolic random graphs
• Data center interconnection networks are not hyperbolic
• Random hypergraph irregularity
• Lack of Gromov-hyperbolicity in colored random networks
• Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
• Geodesic cycles in random graphs
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• A random link via bridge position is hyperbolic

This page was built for publication: On the hyperbolicity of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405243)