×

Gromov hyperbolicity in Cartesian product graphs. (English) Zbl 1268.05172

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\). If \(X\) is hyperbolic, 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}\}\).
In this paper we characterize the product graphs \(G_1 \times G_2\) which are hyperbolic, in terms of \(G_1\) and \(G_2\): the product graph \(G_1\times G_2\) is hyperbolic if and only if \(G_1\) is hyperbolic and \(G_2\) is bounded or \(G_2\) is hyperbolic and \(G_1\) is bounded. We also prove some sharp relations between the hyperbolicity constant of \(G_1 \times G_2\), \(\delta(G_1)\), \(\delta(G_2)\) and the diameters of \(G_1\) and \(G_2\) (and we find families of graphs for which the inequalities are attained). Furthermore, we obtain the precise value of the hyperbolicity constant for many product graphs.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C63 Infinite graphs
53C22 Geodesics in global differential geometry
53C23 Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces
Full Text: DOI

References:

[1] Balogh Z M and Buckley S M, Geometric characterizations of Gromov hyperbolicity, Invent. Math. 153 (2003) 261–301 · Zbl 1059.30038 · doi:10.1007/s00222-003-0287-6
[2] Bermudo S, Rodríguez J M, Sigarreta J M and Vilaire J-M, Mathematical properties of Gromov hyperbolic graphs, to appear in AIP Conference Proceedings (2010) · Zbl 1279.05017
[3] Bermudo S, Rodríguez J M, Sigarreta J M and Vilaire J-M, Gromov hyperbolic graphs, preprint
[4] Bermudo S, Rodríguez J M, Sigarreta J M and Tourís E, Hyperbolicity and complement of graphs, preprint · Zbl 1242.05061
[5] Bonk M, Heinonen J and Koskela P, Uniformizing Gromov hyperbolic spaces, Astérisque 270 (2001) 99 pp. · Zbl 0970.30010
[6] Bowditch B H, Notes on Gromov’s hyperobolicity criterion for path-metric spaces. Group theory from a geometrical viewpoint, Trieste, 1990 (eds) E Ghys, A Haefliger and A Verjovsky (River Edge, NJ: World Scientific) (1991) pp. 64–167
[7] Brinkmann G, Koolen J and Moulton V, On the hyperbolicity of chordal graphs, Ann. Comb. 5 (2001) 61–69 · Zbl 0985.05021 · doi:10.1007/s00026-001-8007-7
[8] Chepoi V, Dragan F F, Estellon B, Habib M and Vaxes Y, Notes on diameters, centers and approximating trees of {\(\delta\)}-hyperbolic geodesic spaces and graphs, Electr. Notes Discrete Math. 31 (2008) 231–234 · Zbl 1267.05077 · doi:10.1016/j.endm.2008.06.046
[9] Frigerio R and Sisto A, Characterizing hyperbolic spaces and real trees, Geom Dedicata 142 (2009) 139–149 · Zbl 1180.53045 · doi:10.1007/s10711-009-9363-4
[10] Ghys E and de la Harpe P, Sur les Groupes Hyperboliques d’après Mikhael Gromov, Progress in Mathematics 83 (Boston, MA: Birkhauser Boston Inc.) (1990) · Zbl 0731.20025
[11] Gromov M, Hyperbolic groups, in ’Essays in group theory’ (ed) S M Gersten (MSRI Publ., Springer) (1987) vol. 8, pp. 75–263
[12] Gromov M (with appendices by M Katz, P Pansu and S Semmes), Metric structures for Riemannian and non-Riemannnian spaces, Progress in Mathematics (Birkhäuser) (1999) vol. 152
[13] Hästö P A, Gromov hyperbolicity of the j G and $\(\backslash\)tilde J_G$ metrics, Proc. Am. Math. Soc. 134 (2006) 1137–1142 · Zbl 1089.30044 · doi:10.1090/S0002-9939-05-08053-6
[14] Hästö P A, Lindén H, Portilla A, Rodríguez J M and Tourís E, Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics, preprint · Zbl 1262.30044
[15] Hästö P A, Portilla A, Rodríguez J M and Tourís E, Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains, to appear in Bull. London Math. Soc. · Zbl 1195.30061
[16] Hästö P A, Portilla A, Rodríguez J M and Tourís E, Comparative Gromov hyperbolicity results for the hyperbolic and quasihyperbolic metrics, to appear in Complex Variables and Elliptic Equations · Zbl 1190.30030
[17] Hästö P A, Portilla A, Rodríguez JM and Tourís E, Uniformly separated sets and Gromov hyperbolicity of domains with the quasihyperbolic metric, to appear in Medit. J. Math.
[18] Jonckheere E A, Controle du trafic sur les reseaux a geometrie hyperbolique-Une approche mathematique a la securite de l’acheminement de l’information, Journal Europeen de Systemes Automatises 37(2) (2003) 145–159 · doi:10.3166/jesa.37.145-159
[19] Jonckheere E A and Lohsoonthorn P, Geometry of network security, American Control Conf. ACC (2004) 111–151
[20] Jonckheere E A, Lohsoonthorn P and Bonahon F, Scaled Gromov hyperbolic graphs, J. Graph Theory 2 (2007) 157–180 · Zbl 1160.05017
[21] Koolen J H and Moulton V, Hyperbolic Bridged Graphs, Europ. J. Combinatorics 23 (2002) 683–699 · Zbl 1027.05035 · doi:10.1006/eujc.2002.0591
[22] Michel J, Rodríguez J M, Sigarreta J M and Villeta M, Hyperbolicity and parameters of graphs, to appear in Ars Combinatoria · Zbl 1265.05200
[23] Oshika K, Discrete groups (AMS Bookstore) (2002)
[24] Portilla A, Rodríguez J M and Tourís E, Gromov hyperbolicity through decomposition of metric spaces II, J. Geom. Anal. 14 (2004) 123–149 · Zbl 1047.30028 · doi:10.1007/BF02921869
[25] Portilla A and Tourís E, A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat. 53 (2009) 83–110 · Zbl 1153.53320 · doi:10.5565/PUBLMAT_53109_04
[26] Rodríguez J M, Sigarreta J M, Vilaire J-M and Villeta M, On the hyperbolicity constant in graphs, preprint · Zbl 1226.05147
[27] Rodríguez J M and Tourís E, Gromov hyperbolicity through decomposition of metric spaces, Acta Math. Hungar. 103 (2004) 53–84
[28] Rodríguez J M and Tourís E, A new characterization of Gromov hyperbolicity for Riemann surfaces, Publ. Mat. 50 (2006) 249–278 · Zbl 1111.53033 · doi:10.5565/PUBLMAT_50206_01
[29] Rodríguez J M and Tourís E, Gromov hyperbolicity of Riemann surfaces, Acta Math. Sinica 23 (2007) 209–228 · Zbl 1115.30050 · doi:10.1007/s10114-005-0547-z
[30] Tourís E, Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, preprint
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.