Eccentricity terrain of δ-hyperbolic graphs

A graph G = (V, E) is delta-hyperbolic if for any four vertices u, v, w, x, the two larger of the three distance sums d(u, v) + d(w, x), d(u, w) + d(v, x), d(u, x) + d(v, w) differ by at most 2 delta >= 0. This paper describes the eccentricity terrain of a delta-hyperbolic graph. The eccentricity function e(G) (v) = max{d(v, u) : u is an element of V} partitions vertices of G into eccentricity layers C-k(G) = {v is an element of V : e(G)(v) = rad(G) k}, k is an element of N, where rad(G) = min{e(G)(v) : v is an element of V} is the radius of G. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of beta-pseudoconvexity, which implies Gromov's epsilon-quasiconvexity, and illustrates the abundance of pseudoconvex sets in delta-hyperbolic graphs. It shows that all sets C-<= k(G) = {v is an element of V : e(G) (v) <= rad(G) k}, k is an element of N, are (2 delta - 1)-pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. (C) 2020 Elsevier Inc. All rights reserved.