Published 2014 | Version v1
Journal article

ON THE HYPERBOLICITY OF RANDOM GRAPHS

Description

Let G = (V, E) be a connected graph with the usual (graph) distance metric d . 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 determine precisely the value of this hyperbolicity for most binomial random graphs.

Abstract

International audience

Additional details

Identifiers

URL
https://hal.science/hal-01143661
URN
urn:oai:HAL:hal-01143661v1