Gromov hyperbolicity in strong product graphs

Carballosa W. Casablanca, Rocío M. de la Cruz A. Rodriguez J.M.
Electronic Journal of Combinatorics
Volumen 20
2013-07-30
Citas: 13
Abstract
If X is a geodesic metric space and x1, x2, x3 ? X, a geodesic triangle T = {x1, x2, x3} 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) = inf {?? 0: X is ?-hyperbolic}: In this paper we characterize the strong product of two graphs G1 {squared times} G2 which are hyperbolic, in terms of G1 and G2: the strong product graph G1{squared times}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 {squared times}G2), ? (G1), ? (G2) and the diameters of G1 and G2 (and we find families of graphs for which the inequalities are attained). Furthermore, we obtain the exact values of the hyperbolicity constant for many strong product graphs.
Geodesics, Gromov hyperbolicity, Infinite graphs, Strong product graphs
Datos de publicaciones obtenidos de Scopus