Search

The concept of Gromov hyperbolicity grasps the essence of negatively curved spaces like the classical hyperbolic space and Riemannian manifolds of negative sectional curvature. It is remarkable that a simple concept leads to such a rich general theory. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of any geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In this Ph. D. Thesis we characterize the hyperbolicity constant of interval graphs and circular-arc graphs. Likewise, we provide relationships between dominant sets and the hyperbolicity constant. Finally, we study the invariance of the hyperbolicity constant when the graphs are transformed by several operators. Programa de Doctorado en Ingeniería Matemática por la Universidad Carlos III de Madrid Presidente: Domingo de Guzmán Pestana Galván.- Secretaria: Ana Portilla Ferreira.- Vocal: Eva Tourís Lojo

Sea X un espacio métrico geodésico y x₁, x₂, x₃ ∈ X. Un triángulo geodésico T = {x₁, x₂, x₃} es la unión de tres geodésicas [x₁x₂], [x₂x₃] y [x₃x₁] de X. El espacio X es δ-hiperbólico (en el sentido de Gromov) si todo lado de T está contenido en la δ-vecindad de la unión de los otros dos lados, para todo triángulo geodésico T de X. Se denota por δ(X) la constante de hiperbolicidad óptima de X, es decir, δ(X) := inf{δ ≥ 0 : X es δ-hiperbólico}. El estudio de los grafos hiperbólicos es un tema interesante dado que la hiperbolicidad de un espacio métrico geodésico es equivalente a la hiperbolicidad de un grafo más sencillo asociado al espacio. Uno de los principales objetivos de esta tesis de doctorado es obtener información cuantitativa acerca de la constante de hiperbolicidad de varios productos de grafos. Estas desigualdades permiten obtener un resultado cualitativo importante: la caracterización de la hiperbolicidad de varios productos de grafos en términos de la hiperbolicidad de sus componentes. En este trabajo caracterizamos los productos fuertes de grafos G₁ ⊠ G₂ hiperbólicos, en términos de G₁ y G₂: el producto fuerte G₁ ⊠G₂ es hiperbólico si y sólo si uno de los factores es hiperbólico y el otro está acotado. También probamos algunas relaciones óptimas entre δ(G₁ ⊠ G₂), δ(G₁), δ(G₂) y los diámetros de G₁ y G₂ (y encontramos familias de grafos para los cuales se alcanzan las desigualdades). Obtenemos el valor exacto de la constante de hiperbolicidad para varios productos fuertes de grafos. También caracterizamos los productos lexicográficos de grafos G₁ ◦ G₂ hiperbólicos, en términos de G₁ y G₂: el producto lexicográfico G₁ ◦ G₂ es hiperbólico si y sólo si G₁ es hiperbólico, a menos que G₁ sea un grafo trivial; si G₁ es trivial, entonces G₁ ◦ G₂ es hiperbólico si y sólo si G₂ es hiperbólico. En particular, obtenemos las desigualdades δ(G₁) ≤ δ(G₁ ◦ G₂) ≤ δ(G₁) + 3/2 si G₁ es un grafo no trivial, y encontramos familias de grafos para las cuales se alcanzan estas desigualdades. Además, caracterizamos las sumas cartesianas de grafos G₁ ⊕ G₂ hiperbólicas: G₁ ⊕ G₂ es siempre hiperbólica, a menos que G₁ ó G₂ sea el grafo trivial, y en este último caso G₁ ⊕ G₂ es hiperbólica si y sólo si G₂ ó G₁ es hiperbólico, respectivamente. Obtenemos las desigualdades óptimas 1 ≤ δ(G₁ ⊕ G₂) ≤ 3/2 para todos los grafos G₁, G₂ no triviales. Además, caracterizamos las sumas cartesianas de grafos con δ(G₁⊕G₂) = 1, con δ(G₁⊕G₂) = 5/4 y con δ(G₁ ⊕ G₂) = 3/2. También encontramos el valor exacto de la constante de hiperbolicidad para las sumas cartesianas de diversas familias de grafos. Finalmente, probamos que si el producto directo de grafos G₁×G₂ es hiperbólico, entonces uno de los factores es hiperbólico y el otro factor está acotado. También probamos que esta condición necesaria para la hiperbolicidad es, de hecho, una caracterización en muchos casos. En otros casos, encontramos caracterizaciones que no son tan simples. Además, obtenemos buenas cotas para la constante de hiperbolicidad del producto directo de varias clases de grafos importantes., If X is a geodesic metric space and x₁, x₂, x₃ ∈ X, a geodesic triangle T = {x₁, x₂, x₃} is the union of the three geodesics and [x₁x₂], [x₂x₃] y [x₃x₁] 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 hyperbolicity constant of several products of graphs. These inequalities allow to obtain other main results, which characterize 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 G₁ ⊠ G₂ which are hyper-bolic, in terms of G₁ and G₂: the strong product graph G₁ ⊠ G₂ 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 δ(G₁ ⊠ G₂), δ(G₁), δ(G₂) and the diameters of G₁ and G₂ (and we find 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 G₁ ◦ G₂ which are hyperbolic, in terms of G₁ and G₂: the lexicographic product graph G₁ ◦ G₂ is hyperbolic if and only if G₁ is hyperbolic, unless if G₁ is a trivial graph; if G₁ is trivial, then G₁ ◦ G₂ is hyperbolic if and only if G₂ is hyperbolic. In particular, we obtain that δ(G₁) ≤ δ(G₁ ◦ G₂) ≤ δ(G₁) +3/2 if G₁ is not a trivial graph, and we find families of graphs for which the inequalities are attained. Besides, we characterize the hyperbolic product graphs for the Cartesian sum G₁ ⊕ G₂: G₁ ⊕ G₂ is always hyperbolic, unless either G₁ or G₂ is the trivial graph; if G₁ or G₂ is the trivial graph, then G₁ ⊕ G₂ is hyperbolic if and only if G₂ or G₁ is hyperbolic, respectively. We also obtain the sharp inequalities 1 ≤ δ(G₁ ⊕ G₂) ≤ 3/2 for every non-trivial graphs G₁, G₂. Besides, we characterize the Cartesian sums with δ(G₁⊕G₂) = 1, with δ((G₁⊕G₂) = 5/4 and with δ(G₁⊕G₂) = 3/2. Furthermore, we obtain the precise value of the hyperbolicity constant of the Cartesian sum of many graphs. Finally, we prove that if the direct product G₁×G₂ 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 good bounds for the hyperbolicity constant of the direct product of some important graphs., Programa Oficial de Doctorado en Ingeniería Matemática, Presidente: Domingo de Guzmán Pestana Galván.- Secretario: Ana María Portilla Ferreira.- Vocal: Eva Touris Lojo

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., Sea X un espacio métrico geodésico y x1, x2, x3 ∈ X. Un triángulo geodésico T = {x1, x2, x3} es la unión de tres geodésicas [x1x2], [x2x3] y [x3x1] de X. El espacio X es δ- hiperbólico (en el sentido de Gromov) si todo lado de T está contenido en la δ-vecindad de la unión de los otros dos lados, para todo triángulo geodésico T de X. Se denota por δ(X) a la constante de hiperbolicidad óptima de X, es decir, δ(X) := inf{δ ≥ 0 : X es δ-hiperbólico }. El estudio de los grafos hiperbólicos es un tema interesante dado que la hiperbolicidad de un espacio métrico geodésico es equivalente a la hiperbolicidad de un grafo más sencillo asociado al espacio. Uno de los principales objetivos de esta Tesis Doctoral es obtener información cuantitativa sobre la variación de la constante de hiperbolicidad del grafo G \ e que se obtiene del grafo G mediante la eliminación de una arista arbitraria e de él. Estas desigualdades permiten caracterizar, de forma cuantitativa, la hiperbolicidad de cualquier grafo en términos de su hiperbolicidad local. En esta memoria se obtene información acerca de la constante de hiperbolicidad del grafo línea L(G) en términos de propiedades del grafo G. En particular, se obtienen los siguientes resultados cualitativos: un grafo G es hiperbólico si y sólo si L(G) es hiperbólico; si {Gn} es una T-descomposición de G, el grafo línea L(G) es hiperbólico si y sólo si supn δ(L(Gn)) es finito. Además, se obtienen resultados cuantitativos cuando las aristas de G y L(G) tienen longitud k. Se demuestra que g(G)/4 ≤ δ(L(G)) ≤ c(G)/4 + 2k, donde g(G) es el cuello de G y c(G) es su circunferencia. También se prueba que δ(L(G)) ≥ sup{L(g) : g es un ciclo isométrico de G}/4. Igualmente, se obtienen cotas para δ(G) + δ(L(G)) y se caracterizan los grafos G tales que δ(L(G)) < k. Por otra parte, se consideran grafos G con aristas de longitudes arbitrarias, y L(G) con aristas de longitudes no constante. En particular, se demuestra que los ciclos de G se transforman isométricamente en ciclos de L(G) con la misma longitud. También se obtiene la relación δ(G) ≤ δ(L(G)) ≤ 5δ(G) + 3lmax, donde lmax := supe∈E(G) L(e). Este resultado prueba la monotonía de la constante de hiperbolicidad bajo una transformación no trivial (el grafo línea de un grafo). También, se obtienen criterios que permiten decidir, para una clase amplia de grafos, cuando son estos hiperbólicos o no. Se presta especial atención en los grafos planares que son la “frontera” (el 1-esqueleto) de una teselación del plano euclídeo. Además, se prueba que los grafos que se obtienen como 1-esqueleto de un CW 2-complejo general son hiperbólicos si y sólo si su grafo dual es hiperbólico. Uno de los principales problemas en este área es relacionar la hiperbolicidad de un grafo con otras propiedades de la teoría de grafos. En este trabajo se extiende de dos maneras (arista-cordalidad y camino-cordalidad) la definición clásica de cordalidad con el fin de relacionar esta propiedad con la hiperbolicidad. De hecho, se demuestra que todo grafo arista-cordal es hiperbólico y que todo grafo hiperbólico es camino-cordal. También, se demuestra que todo grafo cúbico camino-cordal (con constante pequeña de camino-cordalidad) es hiperbólico. Algunos trabajos previos caracterizan la hiperbolicidad de productos de grafos (para el producto cartesiano, el producto fuerte y el producto lexicográfico) en términos de propiedades de los grafos factores. En el último capítulo, se caracteriza la hiperbolicidad de dos productos de grafos: el grafo join G1 ⊎ G2 y el corona G1 ⋄ G2. El grafo join G1 ⊎ G2 siempre es hiperbólico, y el corona G1 ⋄ G2 es hiperbólico si y sólo si G1 es hiperbólico. Además, obtenemos fórmulas sencillas para la constante de hiperbolicidad del grafo join G1 ⊎ G2 y del corona G1 ⋄ G2.