Click here to view fulltext PDF

Permanent link:
https://www.ias.ac.in/article/fulltext/pmsc/129/01/0005

Lexicographic product graphs; geodesics; Gromov hyperbolicity; infinite 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.

WALTER CARBALLOSA^{1 2} AMAURIS DE LA CRUZ³ JOSÉ M RODRÍGUEZ³

1. Department of Mathematics and Statistics, Florida International University, 11200 SW 8th Street, Miami, FL 33199, USA
2. Department of Mathematics, Miami Dade College, 300 NE Second Ave., Miami, FL 33132, USA
3. Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Leganés, Madrid, Spain

Published

1 February 2019

Manuscript received

14 May 2017

Manuscript revised

19 July 2017

Accepted

26 July 2017

Early published

Unedited version published online

Final version published online

17 December 2018