کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646785 1342313 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Small values of the hyperbolicity constant in graphs
ترجمه فارسی عنوان
مقادیر کوچک از ثابت هذلولی در نمودارها
کلمات کلیدی
نمودارها، نمودارهای بی نهایت، زمین شناسی غربال گرروم، هذیانگرایی ثابت است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

If XX 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 sharpest hyperbolicity constant of XX, i.e., δ(X):=inf{δ≥0:X  is  δ-hyperbolic}. In the study of any parameter on graphs it is natural to study the graphs for which this parameter has small values. In this paper we study the graphs with small hyperbolicity constant, i.e., the graphs which are like trees (in the Gromov sense). We obtain simple characterizations of the graphs GG with δ(G)=1δ(G)=1 and δ(G)=54 (the case δ(G)<1δ(G)<1 is known). Also, we give a necessary condition in order to have δ(G)=32 (we know that δ(G)δ(G) is a multiple of 14). Although it is not possible to obtain bounds for the diameter of graphs with small hyperbolicity constant, we obtain such bounds for the effective diameter if δ(G)<32. This is the best possible result, since we prove that it is not possible to obtain similar bounds if δ(G)≥32.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 12, 6 December 2016, Pages 3073–3084
نویسندگان
, , , ,