On the hyperbolicity constant in graphs |
| |
Authors: | José M Rodríguez José M Sigarreta Jean-Marie Vilaire María Villeta |
| |
Institution: | aDepartamento de Matemáticas, Universidad Carlos III de Madrid, Av. de la Universidad 30, 28911 Leganés, Madrid, Spain;bFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame 5, Col. La Garita, Acapulco, Guerrero, Mexico;cDepartamento de Estadística e Investigación Operativa III, Universidad Complutense de Madrid, Av. Puerta de Hierro s/n., 28040 Madrid, Spain |
| |
Abstract: | If X is a geodesic metric space and x1,x2,x3∈X, a geodesic triangleT={x1,x2,x3} is the union of the three geodesics x1x2], x2x3] and x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if, for every geodesic triangle T in X, every side of T is contained in a δ-neighborhood of the union of the other two sides. We denote by δ(X) the sharpest hyperbolicity constant of X, i.e. . In this paper, we obtain several tight bounds for the hyperbolicity constant of a graph and precise values of this constant for some important families of graphs. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its number of edges, diameter and cycles. As a consequence of our results, we show that if G is any graph with m edges with lengths , then , and if and only if G is isomorphic to Cm. Moreover, we prove the inequality for every graph, and we use this inequality in order to compute the precise value δ(G) for some common graphs. |
| |
Keywords: | Graphs Connectivity Geodesics Gromov Hyperbolicity |
本文献已被 ScienceDirect 等数据库收录! |
|