Gromov hyperbolicity in lexicographic product graphs
WALTER CARBALLOSA AMAURIS DE LA CRUZ JOSÉ M RODRÍGUEZ
Click here to view fulltext PDF
Permanent link:
https://www.ias.ac.in/article/fulltext/pmsc/129/01/0005
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^{3} ^{} JOSÉ M RODRÍGUEZ^{3} ^{}
Current Issue
Volume 129 | Issue 5
November 2019
Click here for Editorial Note on CAP Mode
© 2017-2019 Indian Academy of Sciences, Bengaluru.