On the hyperbolicity constant in graphs

If X is a geodesic metric space and x₁,x₂,x₃∈X, a geodesic triangleT={x₁,x₂,x₃} is the union of the three geodesics [x₁x₂], [x₂x₃] and [x₃x₁] 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. . 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 , then , and if and only if G is isomorphic to C_m. Moreover, we prove the inequality for every graph, and we use this inequality in order to compute the precise value δ(G) for some common graphs.