New inequalities on the hyperbolicity constant of line graphs Articles uri icon

publication date

  • October 2016

start page

  • 367

end page

  • 386

volume

  • 129

international standard serial number (ISSN)

  • WWWW-0074

abstract

  • If X is a geodesic metric space and x(1), x(2), x(3) is an element of 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 >= 0 : X is delta-hyperbolic}. The main result of this paper is the inequality delta(G) <= delta(L(G)) for the line graph L(G) of every graph G. We prove also the upper bound delta(L(C(G)) <= 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) <= delta(L(G)) <= 5 delta(G) + 5k/2.

keywords

  • Infinite Graphs; Line Graphs; Geodesics; Gromov Hyperbolicity; Quasihyperbolic metrics; Denjoy domains; Surfaces