On the hyperbolicity constant in graphs

If X is a geodesic metric space and x1,x2,x3∈X, a geodesic triangle T={x1,x2,x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if, for every geodesic triangle T in X, every side of T is contained in a δ-neighborhood of the union of the other two sides. We denote by δ(X) the sharpest hyperbolicity constant of X, i.e. δ(X)≔inf{δ≥0:X is δ-hyperbolic}. In this paper, we obtain several tight bounds for the hyperbolicity constant of a graph and precise values of this constant for some important families of graphs. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its number of edges, diameter and cycles. As a consequence of our results, we show that if G is any graph with m edges with lengths {lk}k=1m, then δ(G)≤∑k=1mlk/4, and δ(G)=∑k=1mlk/4 if and only if G is isomorphic to Cm. Moreover, we prove the inequality δ(G)≤12diamG for every graph, and we use this inequality in order to compute the precise value δ(G) for some common graphs.