On the hyperbolicity of random graphs

MaRDI QIDQ405243zbMATH OpenFDO

Authors D. Mitsche, Paweł Prałat

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1401.5678, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p39

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

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)

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.

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

Cites work

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

Cited in

(13)

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

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)