Search

A graph H is a minor of a graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. 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 in this work is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph G/e obtained from the (simple or non-simple) graph G by contracting an arbitrary edge e from it. We prove that H is hyperbolic if and only if G is hyperbolic, for many minors H of G, even if H is obtained from G by contracting and/or deleting infinitely many edges. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and $$x_1,x_2,x_3$$ are three points in $$X$$ , a geodesic triangle $$T=\{x_1,x_2,x_3\}$$ is the union of three geodesics $$[x_1x_2]$$ , $$[x_2x_3]$$ and $$[x_3x_1]$$ in $$X$$ . The space $$X$$ is $$\delta $$ - hyperbolic $$($$ in the Gromov sense $$)$$ if any side of $$T$$ is contained in a $$\delta $$ -neighborhood of the union of the two other sides, for every geodesic triangle $$T$$ in $$X$$ . 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. In this paper 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. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and x1,x2,x3∈X, a geodesic triangleT={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 a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. δ(X)=inf{δ≥0:Xisδ-hyperbolic}. In this paper, we characterize the lexicographic product of two graphs G1∘G2 which are hyperbolic, in terms of G1 and G2: the lexicographic product graph G1∘G2 is hyperbolic if and only if G1 is hyperbolic, unless if G1 is a trivial graph (the graph with a single vertex); if G1 is trivial, then G1∘G2 is hyperbolic if and only if G2 is hyperbolic. In particular, we obtain the sharp inequalities δ(G1)≤δ(G1∘G2)≤δ(G1)+3/2 if G1 is not a trivial graph, and we characterize the graphs for which the second inequality is attained. [ABSTRACT FROM AUTHOR]