Gromov hyperbolicity in lexicographic product graphs

[摘要] 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_{1}x_{2}], [x_{2}x_{3}]$ and $[x_{3}x_{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$ is $\delta$-hyperbolic\}. In this paper, we characterize the lexicographic product of two graphs $G_{1} \circ G_{2}$ which are hyperbolic, in terms of $G_{1}$ and $G_{2}:$ the lexicographic product graph $G_{1} \circ G_{2}$ is hyperbolic if and only if $G_{1}$ is hyperbolic, unless if $G_{1}$ is a trivial graph (the graph with a single vertex); if $G_{1}$ is trivial, then $G_{1} \circ G_{2}$ is hyperbolic if and only if $G_{2}$ is hyperbolic. In particular, we obtain the sharp inequalities $\delta(G_{1}) \leq \delta(G_{1} \circ G_{2}) \leq \delta(G_{1}) + 3/2$ if $G_{1}$ 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