RT Dissertation/Thesis
T1 Gromov hiperbolicity in graphs
A1 Carballosa Torres, Walter
AB If X is a geodesic metric space and x1, x2, x3 ∈ X, a geodesic triangle T = {x1, x2, x3} isthe 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 unionof the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharphyperbolicity constant of X, i.e., δ(X) := inf{δ ≥ 0 : X is δ-hyperbolic } . The study ofhyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric spaceis 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 thedistortion of the hyperbolicity constant of the graph G \ e obtained from the graph G bydeleting 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 localhyperbolicity.In this work we also obtain information about the hyperbolicity constant of the linegraph L(G) in terms of properties of the graph G. In particular, we prove qualitative resultsas the following: a graph G is hyperbolic if and only if L(G) is hyperbolic; if {Gn} is aT-decomposition of G ({Gn} are simple subgraphs of G), the line graph L(G) is hyperbolicif and only if supn δ(L(Gn)) is finite. Besides, we obtain quantitative results when k isthe length of the edges of G and L(G). Two of them are quantitative versions of ourqualitative 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, wecharacterize the graphs G with δ(L(G)) < k.Furthermore, we consider G with edges of arbitrary lengths, and L(G) with edges ofnon-constant lengths. In particular, we prove that a cycle of the graph G is transformedisometrically 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 themonotony of the hyperbolicity constant under a non-trivial transformation (the line graphof a graph).Also, we obtain criteria which allow us to decide, for a large class of graphs, whetherthey 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 provethat 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 propertieson graph theory. We extend in two ways (edge-chordality and path-chordality) theclassical 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 (withsmall 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 simpleformulae for the hyperbolicity constant of the graph join G1 ⊎ G2 and the corona G1 ⋄ G2. ------------------------------------------------------------------------------
AB 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 grafolí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 setransforman 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 grafocon 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 finde 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 elproducto 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.
YR 2014
FD 2014-01
LK https://hdl.handle.net/10016/18704
UL https://hdl.handle.net/10016/18704
LA eng
DS e-Archivo
RD 1 may. 2024