Gromov hyperbolicity in lexicographic product graphs

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 d- hyperbolic ( in the Gromov sense) if any side of T is contained in a d- neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by d( X) the sharp hyperbolicity constant of X, i. e. d( X) = inf{d = 0 : X is d- hyperbolic}. In this paper, we characterize the lexicographic product of two graphs G1. G2 which are hyperbolic, in terms of G1 and G2: the lexicographic product graph G1. G2 is hyperbolic if and only if G1 is hyperbolic, unless if G1 is a trivial graph ( the graph with a single vertex); if G1 is trivial, then G1. G2 is hyperbolic if and only if G2 is hyperbolic. In particular, we obtain the sharp inequalities d( G1) = d( G1. G2) = d( G1) + 3/ 2 if G1 is not a trivial graph, and we characterize the graphs for which the second inequality is attained.

lexicographic product graphs; geodesics; gromov hyperbolicity; infinite graphs; primary: 05c76; 05c10; secondary: 05c35; 05c63; 05c12; constant; decomposition; metrics; spaces

Gromov hyperbolicity in lexicographic product graphs Articles