Characterization of the hyperbolicity in the lexicographic product Article

Carballosa, W, de la Cruz, A, Rodríguez, JM. (2014). Characterization of the hyperbolicity in the lexicographic product . 46(1), 97-104. 10.1016/j.endm.2014.08.014

cited authors

  • Carballosa, W; de la Cruz, A; Rodríguez, JM

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:Xisδ-hyperbolic}. In this paper we characterize the lexicographic product of two graphs G1G2 which are hyperbolic, in terms of G1 and G2: the lexicographic product graph G1G2 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 G1G2 is hyperbolic if and only if G2 is hyperbolic. In particular, we obtain that δ(G1)≤δ(G1G2)≤δ(G1)+3/2 if G1 is not a trivial graph, and we find families of graphs for which the inequalities are attained.

publication date

  • January 1, 2014

Digital Object Identifier (DOI)

start page

  • 97

end page

  • 104

volume

  • 46

issue

  • 1