Hyperbolicity and complement of graphs

✍ Scribed by Sergio Bermudo; José M. Rodríguez; José M. Sigarreta; Eva Tourís

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 280 KB
• Volume: 24
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2011.05.011

✦ Synopsis

If X is a geodesic metric space and x 1 , x 2 , x 3 ∈ 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 δ-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}. 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. The main aim of this paper is to obtain information about the hyperbolicity constant of the complement graph G in terms of properties of the graph G. In particular, we prove that if diam(V (G)) ≥ 3, then δ(G) ≤ 2, and that the inequality is sharp. Furthermore, we find some Nordhaus-Gaddum type results on the hyperbolicity constant of a graph δ(G).