Publication: Gromov hiperbolicity in graphs
Loading...
Identifiers
Publication date
2014-01
Defense date
2014-01-10
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
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.
Description
Keywords
Hyperbolic graphs, Gromov hyperbolicity