Gromov hyperbolic cubic graphs

✍ Scribed by Domingo Pestana; José M. Rodríguez; José M. Sigarreta; María Villeta

• Book ID: 119990100
• Publisher: SP Versita
• Year: 2012
• Tongue: English
• Weight: 987 KB
• Volume: 10
• Category: Article
• ISSN: 1895-1074
• DOI: 10.2478/s11533-012-0036-4

✦ Synopsis

If X is a geodesic metric space and 1 2 3 ∈ X , a geodesic triangle T = { 1 2 3 } is the union of the three geodesics [

1 2 ], [ 2 3 ] and [ 3 1 ] 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 vertices, we have δ(G) ≤ min {3 /16 + 1 /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.