×

On the hyperbolicity constant in graphs. (English) Zbl 1226.05147

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, for every geodesic triangle \(T\) in \(X\), every side of \(T\) is contained in a \(\delta\)-neighborhood of the union of the other two sides. We denote by \(\delta(X)\) the sharpest hyperbolicity constant of \(X\), i.e., \(\delta(X):= \text{inf}\{\delta\geq 0\): \(X\) is \(\delta\)-hyperbolic}.
In this paper, we obtain several tight bounds for the hyperbolicity constant of a graph and precise values of this constant for some important families of graphs. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its number of edges, diameter and cycles. As a consequence of our results, we show that if \(G\) is any graph with \(m\) edges with lengths \(\{l_k\}^m_{k=1}\), then \(\delta(G)\leq \sum^m_{k=1} l_k/4\), and \(\delta(G)=\sum^m_{k=1} l_k/4\) if and only if \(G\) is isomorphic to \(C_m\). Moreover, we prove the inequality \(\delta(G)\leq {1\over 2}\,\text{diam\,}G\) for every graph, and we use this inequality in order to compute the precise value \(\delta(G)\) for some common graphs.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarez, V.; Portilla, A.; Rodríguez, J. M.; Tourís, E., Gromov hyperbolicity of Denjoy domains, Geom. Dedicata, 121, 221-245 (2006) · Zbl 1115.53030
[2] S. Bermudo, H. Fernau, J.M. Rodríguez, J.M. Sigarreta, Discretization of the hyperbolicity constant. Preprint.; S. Bermudo, H. Fernau, J.M. Rodríguez, J.M. Sigarreta, Discretization of the hyperbolicity constant. Preprint.
[3] Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M., Mathematical properties of Gromov hyperbolic graphs, AIP Conf. Proc., 281, 575-578 (2010)
[4] S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, J.-M. Vilaire, Gromov hyperbolic Graphs (submitted for publication).; S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, J.-M. Vilaire, Gromov hyperbolic Graphs (submitted for publication).
[5] S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, E. Tourís, Hyperbolicity and complement of graphs (submitted for publication).; S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, E. Tourís, Hyperbolicity and complement of graphs (submitted for publication).
[6] Balogh, Z. M.; Bonk, M., Gromov hyperbolicity and the Kobayashi metric on strictly pseudoconvex domains, Comment. Math. Helv., 75, 504-533 (2000) · Zbl 0986.32012
[7] Balogh, Z. M.; Buckley, S. M., Geometric characterizations of Gromov hyperbolicity, Invent. Math., 153, 261-301 (2003) · Zbl 1059.30038
[8] Benoist, Y., Convexes hyperboliques et fonctions quasisymétriques, Publ. Math. Inst. Hautes Études Sci., 97, 181-237 (2003) · Zbl 1049.53027
[9] Bonk, M., Quasi-geodesics segments and Gromov hyperbolic spaces, Geom. Dedicata, 62, 281-298 (1996) · Zbl 0864.53031
[10] Bonk, M.; Heinonen, J.; Koskela, P., Uniformizing Gromov hyperbolic spaces, Astérisque, 270 (2001) · Zbl 0970.30010
[11] Bonk, M.; Schramm, O., Embeddings of Gromov hyperbolic spaces, Geom. Funct. Anal., 10, 266-306 (2000) · Zbl 0972.53021
[12] Bowditch, B. H., Notes on Gromov’s hyperobolicity criterion for path-metric spaces, (Ghys, E.; Haefliger, A.; Verjovsky, A., Group Theory from a Geometrical Viewpoint, Trieste, 1990 (1991), World Scientific: World Scientific River Edge, NJ), 64-167 · Zbl 0843.20031
[13] Brinkmann, G.; Koolen, J.; Moulton, V., On the hyperbolicity of chordal graphs, Ann. Comb., 5, 61-69 (2001) · Zbl 0985.05021
[14] Frigerio, R.; Sisto, A., Characterizing hyperbolic spaces and real trees, Geom. Dedicata, 142, 139-149 (2009) · Zbl 1180.53045
[15] Gavoille, G.; Ly, O., Distance labeling in hyperbolic graphs, Lect. Notes Comput. Sci., 3827, 1071-1079 (2005) · Zbl 1175.05050
[16] Ghys, E.; de la Harpe, P., Sur les groupes hyperboliques d’après Mikhael Gromov, (Progress in Mathematics 83 (1990), Birkhäuser Boston Inc: Birkhäuser Boston Inc Boston, MA) · Zbl 0731.20025
[17] Hästö, P. A., Gromov hyperbolicity of the \(j_G\) and \(\widetilde{j}_G\) metrics, Proc. Amer. Math. Soc., 134, 1137-1142 (2006) · Zbl 1089.30044
[18] P.A. Hästö, H. Lindén, A. Portilla, J.M. Rodríguez, E. Tourís, Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics, J. Math. Soc. Japan (in press).; P.A. Hästö, H. Lindén, A. Portilla, J.M. Rodríguez, E. Tourís, Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics, J. Math. Soc. Japan (in press).
[19] Hästö, P. A.; Portilla, A.; Rodríguez, J. M.; Tourís, E., Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains, Bull. London Math. Soc., 42, 282-294 (2010) · Zbl 1195.30061
[20] Hästö, P. A.; Portilla, A.; Rodríguez, J. M.; Tourís, E., Comparative Gromov hyperbolicity results for the hyperbolic and quasihyperbolic metrics, Complex Var. Elliptic Equ., 55, 127-135 (2010) · Zbl 1190.30030
[21] P.A. Hästö, A. Portilla, J.M. Rodríguez, E. Tourís, Uniformly separated sets and Gromov hyperbolicity of domains with the quasihyperbolic metric. Medit. J. Math. in press, (doi:10.1007/s00009-010-0059-7; P.A. Hästö, A. Portilla, J.M. Rodríguez, E. Tourís, Uniformly separated sets and Gromov hyperbolicity of domains with the quasihyperbolic metric. Medit. J. Math. in press, (doi:10.1007/s00009-010-0059-7
[22] E. Jonckheere, P. Lohsoonthorn, A hyperbolic geometry approach to multipath routing, in: Proceedings of the 10th Mediterranean Conference on Control and Automation, MED 2002, Lisbon, Portugal, July, 2002. FA5-1.; E. Jonckheere, P. Lohsoonthorn, A hyperbolic geometry approach to multipath routing, in: Proceedings of the 10th Mediterranean Conference on Control and Automation, MED 2002, Lisbon, Portugal, July, 2002. FA5-1.
[23] Jonckheere, E. A., Contrôle du trafic sur les réseaux à géometrie hyperbolique-Une approche mathématique a la sécurité de l’acheminement de l’information, J. Européen de Systèmes Automatisés, 37, 2, 145-159 (2003)
[24] E.A. Jonckheere, P. Lohsoonthorn, Geometry of network security, in: American Control Conference, ACC, 2004, pp. 111-151.; E.A. Jonckheere, P. Lohsoonthorn, Geometry of network security, in: American Control Conference, ACC, 2004, pp. 111-151.
[25] Jonckheere, E. A.; Lohsoonthorn, P.; Ariaesi, F., Upper bound on scaled Gromov-hyperbolic delta, Appl. Math. Comput., 192, 191-204 (2007) · Zbl 1193.53108
[26] Jonckheere, E. A.; Lohsoonthorn, P.; Bonahon, F., Scaled Gromov hyperbolic graphs, J. Graph Theory, 2, 157-180 (2007) · Zbl 1160.05017
[27] Karlsson, A.; Noskov, G. A., The Hilbert metric and Gromov hyperbolicity, Enseign. Math., 48, 73-89 (2002) · Zbl 1046.53026
[28] Lindén, H., Gromov hyperbolicity of certain conformal invariant metrics, Ann. Acad. Sci. Fenn. Math., 32, 1, 279-288 (2007) · Zbl 1183.30048
[29] Koolen, J. H.; Moulton, V., Hyperbolic bridged graphs, European J. Combin., 23, 683-699 (2002) · Zbl 1027.05035
[30] K. Matsuzaki, J.M. Rodríguez, Twists and Gromov hyperbolicity of Riemann surfaces, Acta Math. Sinica (in press).; K. Matsuzaki, J.M. Rodríguez, Twists and Gromov hyperbolicity of Riemann surfaces, Acta Math. Sinica (in press). · Zbl 1218.30125
[31] J. Michel, J.M. Rodríguez, J.M. Sigarreta, M. Villeta, Hyperbolicity and parameters of graphs, Ars Combin. (in press).; J. Michel, J.M. Rodríguez, J.M. Sigarreta, M. Villeta, Hyperbolicity and parameters of graphs, Ars Combin. (in press).
[32] Michel, J.; Rodríguez, J. M.; Sigarreta, J. M.; Villeta, M., Gromov hyperbolicity in cartesian product graphs, Proc. Indian Acad. Sci. Math. Sci., 120, 5, 1-17 (2010) · Zbl 1268.05172
[33] Oshika, K., Discrete Groups (2002), AMS Bookstore
[34] Portilla, A.; Rodríguez, J. M.; Tourís, E., Gromov hyperbolicity through decomposition of metric spaces II, J. Geom. Anal., 14, 123-149 (2004) · Zbl 1047.30028
[35] Portilla, A.; Rodríguez, J. M.; Tourís, E., Stability of Gromov hyperbolicity, J. Adv. Math Stud., 2, 1-20 (2009) · Zbl 1205.30039
[36] Portilla, A.; Tourís, E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 53, 83-110 (2009) · Zbl 1153.53320
[37] Rodríguez, J. M.; Tourís, E., Gromov hyperbolicity through decomposition of metric spaces, Acta Math. Hung., 103, 53-84 (2004) · Zbl 1051.30036
[38] Rodríguez, J. M.; Tourís, E., A new characterization of Gromov hyperbolicity for Riemann surfaces, Publ. Mat., 50, 249-278 (2006) · Zbl 1111.53033
[39] Rodríguez, J. M.; Tourís, E., Gromov hyperbolicity of Riemann surfaces, Acta Math. Sinica, 23, 209-228 (2007) · Zbl 1115.30050
[40] E. Tourís, Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl. (in press).; E. Tourís, Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl. (in press).
[41] Y. Wu, C. Zhang, Chordality and hyperbolicity of a graph (submitted for publication).; Y. Wu, C. Zhang, Chordality and hyperbolicity of a graph (submitted for publication). · Zbl 1220.05020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.