Repositorio de producción científica de la Universidad de Sevilla

Gromov hyperbolicity in strong product graphs


Advanced Search
Opened Access Gromov hyperbolicity in strong product graphs
Show item statistics
Export to
Author: Carballosa, Walter
Moreno Casablanca, Rocío
Cruz, Amauris de la
Rodríguez, José M.
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2013
Published in: Electronic Journal of Combinatorics, 20 (3)
Document type: Article
Abstract: If X is a geodesic metric space and x1; x2; x3 2 X, a geodesic triangle T = fx1; x2; x3g is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is -hyperbolic (in the Gromov sense) if any side of T is contained in a -neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by (X) the sharp hyperbolicity constant of X, i.e. (X) = inff > 0 : X is -hyperbolic g : In this paper we characterize the strong product of two graphs G1 G2 which are hyperbolic, in terms of G1 and G2: the strong product graph G1 G2 is hyperbolic if and only if one of the factors is hyperbolic and the other one is bounded. We also prove some sharp relations between (G1 G2), (G1), (G2) and the diameters of G1 and G2 (and we nd families of graphs for which the inequalities are attained). Furthermore, we obtain the exact values of the hyperbolicity constant for many strong product graphs.
Cite: Carballosa, W., Moreno Casablanca, R., Cruz, A.d.l. y Rodríguez, J.M. (2013). Gromov hyperbolicity in strong product graphs. Electronic Journal of Combinatorics, 20 (3)
Size: 312.0Kb
Format: PDF


See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)