کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1708435 1012823 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hyperbolicity and complement of graphs
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
Hyperbolicity and complement of graphs
چکیده انگلیسی

If X is a geodesic metric space and x1,x2,x3∈Xx1,x2,x3∈X, a geodesic triangle  T={x1,x2,x3}T={x1,x2,x3} is the union of the three geodesics [x1x2][x1x2], [x2x3][x2x3] and [x3x1][x3x1] in XX. The space XX is δδ-hyperbolic   (in the Gromov sense) if any side of TT is contained in a δδ-neighborhood of the union of the two other sides, for every geodesic triangle TT in XX. We denote by δ(X)δ(X) the sharp hyperbolicity constant of XX, i.e. δ(X)≔inf{δ≥0:X is δ-hyperbolic}δ(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 GG. 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)δ(G).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 24, Issue 11, November 2011, Pages 1882–1887
نویسندگان
, , , ,