On the hyperbolicity constant of line graphs (Q648402): Difference between revisions

Summary: 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 \(\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 study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. The main aim of this paper is to obtain information about the hyperbolicity constant of the line graph \(\mathcal{L}(G)\) in terms of parameters of the graph \(G\). In particular, we prove qualitative results as the following: a graph \(G\) is hyperbolic if and only if \(\mathcal{L}(G)\) is hyperbolic; if \(\{G_n\}\) is a \(T\)-decomposition of \(G\) (\(\{G_n\}\) are simple subgraphs of \(G\)), the line graph \(\mathcal{L}(G)\) is hyperbolic if and only if \(\sup_n \delta(\mathcal{L}(G_n))\) is finite. Besides, we obtain quantitative results. Two of them are quantitative versions of our qualitative results. We also prove that \(g(G)/4 \leq \delta(\mathcal{L}(G)) \leq c(G)/4 + 2\), where \(g(G)\) is the girth of \(G\) and \(c(G)\) is its circumference. We show that \(\delta(\mathcal{L}(G)) \geq \sup\{L(g) : g \text{ is an isometric cycle in }G\} / 4\). Furthermore, we characterize the graphs \(G\) with \(\delta(\mathcal{L}(G)) < 1\).