New Inequalities on the Hyperbolicity Constant of Line 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_1x_2]\), \([x_2x_3]\) and \([x_3x_1]\) in \(X\). The space \(X\) is \(\delta\)-hyperbolic (in the Gromov sense) if any side of \(T\) is contained in a \(5\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}\}\). The main result of this paper is the inequality \(\delta(G) \leq \delta(\mathcal{L}(G))\) for the line graph \(\mathcal{L}(G)\) of every graph \(G\). We prove also the upper bound \(\delta(L(G)) \leq 5\delta(G) + 3l_{\max}\), where \(\max\) is the supremum of the lengths of the edges of \(G\). Furthermore, if every edge of \(G\) has length \(k\), we obtain \(\delta(G) \leq \delta(\mathcal{L}(G)) \leq 5\delta(G) + 5k/2\).