Gromov Hyperbolicity of Regular Graphs

If X is a geodesic metric space and x(1), x(2), x(3) is an element of X, a geodesic triangle T = {x(1), x(2), x(3)} is the union of the three geodesics [x(1)x(2)], [x(2)x(3)] and [x(3)x(1)] in X. The space X is delta-hyperbolic (in the Gromov sense) if any side of T is contained in a delta-neighborhood of the union of the two other sides, for every geodesic triangle T in X. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. Regular graphs are a very interesting class of graphs with many applications. The main aim of this paper is to obtain information about the hyperbolicity constant of regular graphs. We obtain several bounds for this parameter; in particular, we prove that delta(G) <= Delta n/(8(Delta - 1))Ư for any Delta-regular graph G with n vertices. Furthermore, we show that for each Delta >= 2 and every possible value t of the hyperbolicity constant, there exists a Delta-regular graph G with delta(G) = t. We also study the regular graphs G with delta(G) <= 1, i.e., the graphs which are like trees (in the Gromov sense). Besides, we prove some inequalities involving the hyperbolicity constant and domination numbers for regular graphs.

Gromov Hyperbolicity of Regular Graphs Articles