Computing the hyperbolicity constant of a cubic graph

In this paper we obtain information about the hyperbolicity constant of cubic graphs. They are a very interesting class of graphs with many applications; furthermore, they are also very important in the study of Gromov hyperbolicity, since for any graph G with bounded maximum degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. We find some characterizations for the cubic graphs which have small hyperbolicity constants, i.e. the graphs which are like trees (in the Gromov sense). Besides, we obtain bounds for the hyperbolicity constant of the complement graph of a cubic graph; our main result of this kind says that for any finite cubic graph G which is not isomorphic either to K4 or to K3, 3, the inequalities 5k/4≤delta (Ḡ)≤3k/2 hold, if k is the length of every edge in G.

complement graphs; computing hyperbolicity; cubic graphs; gromov hyperbolicity; infinite graphs; complement graphs; cubic graph; hyperbolicity; infinite graph

Computing the hyperbolicity constant of a cubic graph Articles