Gromov Hyperbolicity of Regular Graphs

Abstract

If $X$ is a geodesic metric space and $x_1,x_2,x_3\in 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)\le \frac{\mathrm{\Delta }n}{8(\mathrm{\Delta }-1)+1}$ for any $4$-regular graph $G$ with $n$ vertices. Furthermore, we show that for each $\mathrm{\Delta }\ge 2$ and every possible value $t$ of the hyperbolicity constant, there exists a $\mathrm{\Delta }$-regular graph $G$ with $\delta (G)=t$. We also study the regular graphs $G$ with $\delta (G)\le 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.