{
  "id": "1503.01340",
  "version": "v1",
  "published": "2015-03-04T15:23:27.000Z",
  "updated": "2015-03-04T15:23:27.000Z",
  "title": "Bounds on Gromov Hyperbolicity Constant",
  "authors": [
    "Veronica Hernandez",
    "Domingo Pestana",
    "Jose M. Rodriguez"
  ],
  "categories": [
    "math.CO",
    "math.MG"
  ],
  "abstract": "If $X$ is a geodesic metric space and $x_{1},x_{2},x_{3} \\in X$, 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. $\\delta(X) =\\inf \\{ \\delta\\geq 0:{0.3cm}$ X ${0.2cm}$ $\\text{is} {0.2cm} \\delta \\text{-hyperbolic} \\}.$ 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 $\\mathcal{G}(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):=\\min\\{\\delta(G)\\mid G \\in \\mathcal{G}(n,m) \\}$ and $B(n,m):=\\max\\{\\delta(G)\\mid G \\in \\mathcal{G}(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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-04T15:23:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05A20",
      "05C50"
    ],
    "keywords": [
      "gromov hyperbolicity constant",
      "geodesic triangle",
      "sharp hyperbolicity constant",
      "geodesic metric space",
      "random graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}