Mathematical Properties of Gromov Hyperbolic Graphs

Abstract

In this paper we deal with Gromov hyperbolic graphs. We obtain several tight bounds for the hyperbolicity constant of a graph. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its edge number. 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 show that the study of the hyperbolicity on a graph with loops and multiple edges can be reduced to the study of the hyperbolicity in its subjacent simple graph; we also prove that the study of the hyperbolicity of an arbitrary graph is equivalent to the study of the hyperbolicity of a 3‐regular graph obtained from it by adding some edges and vertices.