Eccentricity terrain of δ-hyperbolic graphs

摘要

A graph G=(V,E) is δ-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δ≥0. This paper describes the eccentricity terrain of a δ-hyperbolic graph. The eccentricity function eG(v)=max⁡{d(v,u):u∈V} partitions vertices of G into eccentricity layers Ck(G)={v∈V:eG(v)=rad(G)+k}, k∈N, where rad(G)=min⁡{eG(v):v∈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 β-pseudoconvexity, which implies Gromov's ϵ-quasiconvexity, and illustrates the abundance of pseudoconvex sets in δ-hyperbolic graphs. It shows that all sets C≤k(G)={v∈V:eG(v)≤rad(G)+k}, k∈N, are (2δ−1)-pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities.