Bounds on Gromov hyperbolicity constant

DOI10.1007/S13398-015-0235-5MaRDI QIDQ326686zbMATH OpenOpenAlexFDO

Authors Verónica Hernández, D. Pestana, 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)

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)

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.

Recommendations

• Bounds on the hyperbolicity constant
• On the hyperbolicity constant in graphs
• Hyperbolicity and parameters of graphs.
• Computing the hyperbolicity constant
• Bounds on Gromov hyperbolicity constant in graphs

Cites work

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

Cited in

(12)

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

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)