Gromov hyperbolic graphs Articles uri icon

publication date

  • August 2013

start page

  • 1575

end page

  • 1585

issue

  • 15

volume

  • 313

International Standard Serial Number (ISSN)

  • 0012-365X

Electronic International Standard Serial Number (EISSN)

  • 1872-681X

abstract

  • In this paper we prove that the study of the hyperbolicity on graphs can be reduced to the study of the hyperbolicity on simpler graphs. In particular, we prove that the study of the hyperbolicity on a graph with loops and multiple edges can be reduced to the study of the hyperbolicity in the same graph without its loops and multiple edges; we also prove that the study of the hyperbolicity on an arbitrary graph is equivalent to the study of the hyperbolicity on a 3-regular graph obtained from it by adding some edges and vertices. Moreover, we study how the hyperbolicity constant of a graph changes upon adding or deleting finitely or infinitely many edges.

keywords

  • graphs; connectivity; geodesics; gromov hyperbolicity