Small values of the hyperbolicity constant in graphs Articles uri icon

publication date

  • December 2016

start page

  • 3073

end page

  • 3084

issue

  • 12

volume

  • 339

international standard serial number (ISSN)

  • 0012-365X

electronic international standard serial number (EISSN)

  • 1872-681X

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 sharpest hyperbolicity constant ofX, i.e., delta(X) := inf{delta >= 0: X is delta-hyperbolic}. In the study of any parameter on graphs it is natural to study the graphs for which this parameter has small values. In this paper we study the graphs with small hyperbolicity constant, i.e., the graphs which are like trees (in the Gromov sense). We obtain simple characterizations of the graphs G with delta(G) = 1 and delta(G) = 5/4 (the case delta(G) < 1 is known). Also, we give a necessary condition in order to have delta(G) = 3/2 (we know that delta(G) is a multiple of 1/4). Although it is not possible to obtain bounds for the diameter of graphs with small hyperbolicity constant, we obtain such bounds for the effective diameter if delta(G) < 3/2. This is the best possible result, since we prove that it is not possible to obtain similar bounds if delta(G) >= 3/2. (C) 2016 Elsevier B.V. All rights reserved.

keywords

  • Graphs; Infinite graphs; Geodesics; Gromov hyperbolicity; Hyperbolicity constant