Gromov hyperbolic cubic graphs

By Domingo Pestana, José M. Rodríguez, Jose Maria Sigarreta, María Villeta. 2012

46 citations recorded by the source corpus.

If X is a geodesic metric space and x1; x2; x3 ∈ X, a geodesic triangle T = {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 any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/587d638d87cff5c739116fcc7da0dc4b0a56a722