Let $G=(V,E)$ be a connected graph with the usual (graph) distance metric $d:V \times V \to \mathbb{N} \cup \{0 \}$. Introduced by Gromov, $G$ is $\delta$-hyperbolic if for every four vertices $u,v,x,y \in 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\delta$. In this paper, we determine precisely the value of this hyperbolicity for most binomial random graphs.
@article{10_37236_4053,
author = {Dieter Mitsche and Pawe{\l} Pra{\l}at},
title = {On the hyperbolicity of random graphs},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/4053},
zbl = {1300.05286},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4053/}
}
TY - JOUR
AU - Dieter Mitsche
AU - Paweł Prałat
TI - On the hyperbolicity of random graphs
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/4053/
DO - 10.37236/4053
ID - 10_37236_4053
ER -
%0 Journal Article
%A Dieter Mitsche
%A Paweł Prałat
%T On the hyperbolicity of random graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4053/
%R 10.37236/4053
%F 10_37236_4053
Dieter Mitsche; Paweł Prałat. On the hyperbolicity of random graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/4053
