Publication: Gromov hyperbolicity of several products of graphs
Loading...
Identifiers
Publication date
2016-09
Defense date
2016-09-08
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
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.
Description
Keywords
Hyperbolicity, Gromov hyperbolicity, Graphs