Computing the hyperbolicity constant of a cubic graph Articles uri icon

publication date

  • September 2014

start page

  • 1897

end page

  • 1910

issue

  • 9

volume

  • 91

international standard serial number (ISSN)

  • 0020-7160

electronic international standard serial number (EISSN)

  • 1029-0265

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 K4 or to K3, 3, the inequalities 5k/4≤delta (Ḡ)≤3k/2 hold, if k is the length of every edge in G.

keywords

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