Article ID Journal Published Year Pages File Type
6423491 Discrete Mathematics 2011 9 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,