Gromov hyperbolic graphs

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. (c) 2013 Elsevier B.V. All rights reserved.