Bounds on Gromov hyperbolicity constant

DOI10.1007/S13398-015-0235-5zbMATH Open1348.05168arXiv1503.01340OpenAlexW1594917025MaRDI QIDQ326686FDOQ326686

D. Pestana, Verónica Hernández, José M. Rodríguez

Publication date: 12 October 2016

Published in: Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A: Matemáticas. RACSAM (Search for Journal in Brave)

Abstract: If $X$ is a geodesic metric space and $x_1,x_2,x_{3}inX$, a geodesic triangle $T=x_1,x_2,x_3$ is the union of the three geodesics $[x_1{x}_2]$, $[x_2{x}_3]$ and $[x_3{x}_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$. If $X$ is hyperbolic, we denote by $delta(X)$ the sharp hyperbolicity constant of $X$, i.e. $$ X $0.2cm$ $$ To compute the hyperbolicity constant is a very hard problem. Then it is natural to try to bound the hyperbolycity constant in terms of some parameters of the graph. Denote by $mathcalG(n,m)$ the set of graphs $G$ with $n$ vertices and $m$ edges, and such that every edge has length $1$. In this work we estimate $A(n,m):=mindelta(G)midGinmathcalG(n,m)$ and $B(n,m):=maxdelta(G)midGinmathcalG(n,m)$. In particular, we obtain good bounds for $B(n,m)$, and we compute the precise value of $A(n,m)$ for all values of $n$ and $m$. Besides, we apply these results to random graphs.

Full work available at URL: https://arxiv.org/abs/1503.01340

zbMATH Keywords

geodesicfinite graphsGromov hyperbolicityhyperbolicity constant

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Signed and weighted graphs (05C22) Structural characterization of families of graphs (05C75) Combinatorial inequalities (05A20)

Cites Work

• Title not available (Why is that?)
• Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Embeddings of Gromov hyperbolic spaces
• Title not available (Why is that?)
• Gromov hyperbolicity through decomposition of metrics spaces. II
• Gromov hyperbolic spaces
• Uniformizing Gromov hyperbolic spaces
• Gromov hyperbolicity of the $j_G$ and ${\tilde \jmath }_G$ metrics
• Distortion of the hyperbolicity constant of a graph
• Geometric characterizations of Gromov hyperbolicity
• Gromov hyperbolicity and the Kobayashi metric on strictly pseudoconvex domains
• Hyperbolic bridged graphs
• Hyperbolicity in median graphs
• Characterization of Gromov hyperbolic short graphs
• Gromov hyperbolic tessellation graphs
• Title not available (Why is that?)
• Gromov hyperbolicity in Cartesian product graphs
• Gromov hyperbolic graphs
• Gromov hyperbolicity in strong product graphs
• Gromov hyperbolic cubic graphs
• Extendability of Large-Scale Lipschitz Maps
• Hyperbolicity in the corona and join of graphs
• Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
• Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces
• Hyperbolicity and chordality of a graph
• On the hyperbolicity of chordal graphs
• On the hyperbolicity constant in graphs
• On the hyperbolicity constant of line graphs
• Hyperbolicity and complement of graphs
• Characterizing hyperbolic spaces and real trees
• A characterization of Gromov hyperbolicity of surfaces with variable negative curvature
• On the hyperbolicity of small-world and treelike random graphs
• Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains
• Lack of Gromov-hyperbolicity in small-world networks
• Scaled Gromov hyperbolic graphs
• Non-Hyperbolicity of Random Graphs with Given Expected Degrees

Cited In (6)

• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• Bounds on Gromov hyperbolicity constant in graphs
• On a classical theorem on the diameter and minimum degree of a graph
• On the hyperbolicity constant of circular-arc graphs
• Recent Results on Hyperbolicity on Unitary Operators on Graphs
• Gromov hyperbolicity of the 𝑗̃_{𝐺} metric and boundary correspondence

This page was built for publication: Bounds on Gromov hyperbolicity constant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326686)