Bounds on Gromov hyperbolicity constant Articles uri icon

publication date

  • September 2016

start page

  • 321

end page

  • 342

issue

  • 2

volume

  • 110

international standard serial number (ISSN)

  • 1578-7303

abstract

  • If X is a geodesic metric space and , a geodesic triangle is the union of the three geodesics , and in X. The space X is -hyperbolic in the Gromov sense if any side of T is contained in a -neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by the sharp hyperbolicity constant of X, i.e., To compute the hyperbolicity constant is a very hard problem. Then it is natural to try to bound the hyperbolicity constant in terms of some parameters of the graph. Denote by the set of (simple) graphs G with n vertices and m edges, and such that every edge has length 1. In this work we estimate and . In particular, we obtain good bounds for B(n, m), and we compute the precise value of A(n, m) for all values of n and m. We also study this problem for non-simple and weighted graphs.

keywords

  • Gromov hyperbolicity; Hyperbolicity constant; Finite graphs; Geodesic; Graphs; Spaces; Metrics; Domains