Resumen de Gromov hyperbolicity of several products of graphs

Amauris de la Cruz Rodriguez

• If X is a geodesic metric space and x1, x2, x3 in 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 delta-hyperbolic (in the Gromov sense) if any side of T is contained in the delta-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by delta(X) the sharp hyperbolicity constant of X, i.e., delta(X) := inf{ delta>= 0 : X is delta-hyperbolic}. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it.

  One of the main aims of this PhD Thesis is to obtain quantitative information about the hyperbolicity constant of several products of graphs. These inequalities allow to obtain other main result, which characterizes in a qualitative way the hyperbolicity of several products of graphs in terms of the hyperbolicity of their components.

  In this work we characterize the strong product of two graphs G1 ⊠G2 which are hyper- bolic, in terms of G1 and G2: the strong product graph G1 ⊠ G2 is hyperbolic if and only if one of the factors is hyperbolic and the other one is bounded. We also prove some sharp relations between (G1 ⊠ G2), delta(G1), delta(G2) and the diameters of G1 and G2 (and we nd families of graphs for which the inequalities are attained). Furthermore, we obtain the exact values of the hyperbolicity constant for many strong product graphs.

  Furthermore, we characterize the lexicographic product of two graphs G1 ◦G2 which are hyperbolic, in terms of G1 and G2: the lexicographic product graph G1 ◦ G2 is hyperbolic if and only if G1 is hyperbolic, unless if G1 is a trivial graph (the graph with a single vertex, which we denote it by E1); if G1 is trivial, then G1 ◦ G2 is hyperbolic if and only if G2 is hyperbolic. In particular, we obtain that  delta(G1) <= delta(G1 ◦ G2)<= delta(G1) + 3/2 if G1 is not a trivial graph, and we nd families of graphs for which the inequalities are attained.

  Besides, we characterize the hyperbolic product graphs for the Cartesian sum G1 by G2: the product G1 by G2 is always hyperbolic, unless either G1 or G2 is the trivial graph; if G1 or G2 is the trivial graph, then G1  G2 is hyperbolic if and only if G2 or G1 is hyperbolic, respectively.

  We also obtain the sharp inequalities 1 <= delta(G1 by G2) <= 3/2 for every non-trivial graphs G1; G2. Besides, we characterize the Cartesian sums with (G1 G2) = 1, (G1 G2) = 5=4 and with delta(G1  G2) = 3/2. Furthermore, we obtain simple formulae for the hyperbolicity constant of the Cartesian sum of many graphs.

  Finally, we prove that if the direct product G1 by G2 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 nd characterizations which are not so simple. Furthermore, we obtain good bounds for the hyperbolicity constant of the direct product of some important graphs.