Quantcast

Small values of the hyperbolicity constant in graphs

Research paper by Sergio Bermudo, José M. Rodríguez, Omar Rosario, José M. Sigarreta

Indexed on: 21 Jul '16Published on: 20 Jul '16Published in: Discrete Mathematics



Abstract

If XX is a geodesic metric space and x1,x2,x3∈Xx1,x2,x3∈X, a geodesic triangle  T={x1,x2,x3}T={x1,x2,x3} is the union of the three geodesics [x1x2][x1x2], [x2x3][x2x3] and [x3x1][x3x1] in XX. The space XX is δδ-hyperbolic   (in the Gromov sense) if any side of TT is contained in a δδ-neighborhood of the union of the two other sides, for every geodesic triangle TT in XX. We denote by δ(X)δ(X) the sharpest hyperbolicity constant of XX, i.e., <img height="15" border="0" style="vertical-align:bottom" width="262" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si23.gif">δ(X):=inf{δ≥0:X  is  δ-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 GG with δ(G)=1δ(G)=1 and <img height="21" border="0" style="vertical-align:bottom" width="62" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si26.gif">δ(G)=54 (the case δ(G)<1δ(G)<1 is known). Also, we give a necessary condition in order to have <img height="21" border="0" style="vertical-align:bottom" width="62" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si28.gif">δ(G)=32 (we know that δ(G)δ(G) is a multiple of <img height="21" border="0" style="vertical-align:bottom" width="8" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si30.gif">14). 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 <img height="21" border="0" style="vertical-align:bottom" width="61" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si31.gif">δ(G)<32. This is the best possible result, since we prove that it is not possible to obtain similar bounds if <img height="21" border="0" style="vertical-align:bottom" width="61" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X16302023-si32.gif">δ(G)≥32.

Figure 10.1016/j.disc.2016.06.013.0.jpg
Figure 10.1016/j.disc.2016.06.013.1.jpg
Figure 10.1016/j.disc.2016.06.013.2.jpg