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 {\it 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$-\emph{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. $δ(X):=\inf\{δ\ge 0: \, X \, \text{ is $δ$-hyperbolic}\,\}\,. $ The main result of this paper is the inequality $\delta (G)\le \delta (\mathcal{L}(G))$ for the line graph $\mathcal{L}(G)$ of every graph $G$. We prove also the upper bound $\delta (\mathcal{L}(G))\le 5\delta (G)+3l_{max}$, where $l_{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)\le \delta (\mathcal{L}(G))\le 5\delta (G)+5k/2$.

Accepted for publication in Ars Combinatoria