Hyperbolicity and Parameters of Graphs

Abstract

If \(X\) is a geodesic metric space and \(x_1, x_2, x_3 \in X\), a geodesic triangle \(T = \{x_1, x_2, x_3\}\) is the union of the three geodesics \([x_1 x_2], [x_2 x_3]\) and \([x_3 x_1]\) in \(X\). The space \(X\) is \(\delta\)-hyperbolic (in the Gromov sense) if any side of \(T\) is contained in a \(\delta\)-neighborhood of the union of the two other sides, for every geodesic triangle \(T\) in \(X\). We denote by \(\delta(X)\) the sharp hyperbolicity constant of \(X\), i.e. \(\delta(X) := \inf\{\delta \geq 0: X \text{ is } \delta\text{-hyperbolic}\}\). In this paper, we find some relations between the hyperbolicity constant of a graph and its order, girth, cycles, and edges. In particular, if \(g\) denotes the girth, we prove \(\delta(G) \geq g(G)/4\) for every (finite or infinite) graph; if \(G\) is a graph of order \(n\) and edges with length \(k\) (possibly with loops and multiple edges), then \(\delta(G) \leq nk/4\). We find a large family of graphs for which the first (non-strict) inequality is in fact an equality; besides, we characterize the set of graphs with \(\delta(G) = nk/4\). Furthermore, we characterize the graphs with edges of length \(k\) with \(\delta(G) < k\).