Computing the hyperbolicity constant of a cubic graph

Abstract

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 K₄ or to K_{3, 3}, the inequalities 5k/4≤δ (Ḡ)≤3k/2 hold, if k is the length of every edge in G.

Keywords:

• computing hyperbolicity
• infinite graphs
• cubic graphs
• complement graphs
• Gromov hyperbolicity

2010 AMS Subject Classifications:

• 05C63
• 05C75

Acknowledgements

Supported in part by a grant from Ministerio de Ciencia e Innovación (MTM 2009-07800), Spain, and a grant from COCYTIEG (GUERRERO), México.