Hyperbolicity of direct products of graphs

arXiv1611.04372MaRDI QIDQ6279727FDOQ6279727

Amauris de La Cruz, Álvaro Martínez-Pérez, José M. Rodríguez, Walter Carballosa

Publication date: 14 November 2016

Abstract: If $X$ is a geodesic metric space and $x_1,x_2,x_{3}inX$, a {it 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$-emph{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$$ Some previous works characterize the hyperbolic product graphs (for the Cartesian, strong, join, corona and lexicographic products) in terms of properties of the factor graphs. However, the problem with the direct product is more complicated. In this paper, we prove that if the direct product $G_{1}imes{G}_2$ is hyperbolic, then one factor is hyperbolic and the other one is bounded. Also, we prove that this necessary condition is, in fact, a characterization in many cases. In other cases, we find characterizations which are not so simple. Furthermore, we obtain formulae or good bounds for the hyperbolicity constant of the direct product of some important graphs.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial inequalities (05A20)

This page was built for publication: Hyperbolicity of direct products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6279727)