Resumen de Gromov hiperbolicity in graphs

Walter Carballosa Torres

• If X is a geodesic metric space and x1, x2, x3 ? 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 ?-hyperbolic (in the Gromov sense) if any side of T is contained in the ?-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by ?(X) the sharp hyperbolicity constant of X, i.e., ?(X) := inf{? ? 0 : X is ?-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 distortion of the hyperbolicity constant of the graph G \ e obtained from the graph G by deleting an arbitrary edge e from it. These inequalities allow to obtain other main result, which characterizes in a quantitative way the hyperbolicity of any graph in terms of local hyperbolicity. In this work we also obtain information about the hyperbolicity constant of the line graph L(G) in terms of properties of the graph G. In particular, we prove qualitative results as the following: a graph G is hyperbolic if and only if L(G) is hyperbolic; if {Gn} is a T-decomposition of G ({Gn} are simple subgraphs of G), the line graph L(G) is hyperbolic if and only if supn ?(L(Gn)) is finite. Besides, we obtain quantitative results when k is the length of the edges of G and L(G). Two of them are quantitative versions of our qualitative results. We also prove that g(G)/4 ? ?(L(G)) ? c(G)/4 + 2k, where g(G) is the girth of G and c(G) is its circumference. We show that ?(L(G)) ? sup{L(g) : g is an isometric cycle in G}/4. Besides, we obtain bounds for ?(G) + ?(L(G)). Also, we characterize the graphs G with ?(L(G)) < k. Furthermore, we consider G with edges of arbitrary lengths, and L(G) with edges of non-constant lengths. In particular, we prove that a cycle of the graph G is transformed isometrically into a cycle of the graph L(G) with the same length. We also prove that ?(G) ? ?(L(G)) ? 5?(G) + 3lmax, where lmax := supe?E(G) L(e). This result implies the monotony of the hyperbolicity constant under a non-trivial transformation (the line graph of a graph). Also, we obtain criteria which allow us to decide, for a large class of graphs, whether they are hyperbolic or not. We are especially interested in the planar graphs which are the “boundary” (the 1-skeleton) of a tessellation of the Euclidean plane. Furthermore, we prove that a graph obtained as the 1-skeleton of a general CW 2-complex is hyperbolic if and only if its dual graph is hyperbolic. One of the main problems on this subject is to relate the hyperbolicity with other properties on graph theory. We extend in two ways (edge-chordality and path-chordality) the classical definition of chordal graphs in order to relate this property with Gromov hyperbolicity. In fact, we prove that every edge-chordal graph is hyperbolic and that every hyperbolic graph is path-chordal. Furthermore, we prove that every path-chordal cubic graph (with small path-chordality constant) is hyperbolic. Some previous works characterize the hyperbolic product graphs (for the Cartesian product, strong product and lexicographic product) in terms of properties of the factor graphs. Finally, we characterize the hyperbolic product graphs for two important kinds of products: the graph join G1 ?G2 and the corona G1 ?G2. The graph join G1 ?G2 is always hyperbolic, and G1 ? G2 is hyperbolic if and only if G1 is hyperbolic. Furthermore, we obtain simple formulae for the hyperbolicity constant of the graph join G1 ? G2 and the corona G1 ? G2. ------------------------------------------------------------------------------