کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874189 | 1441027 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some improved inequalities related to Vizing's conjecture
ترجمه فارسی عنوان
برخی از نابرابری های بهبود یافته مربوط به حدس ویزیز است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تعداد سلطه، شماره سلطنت رومی، نمودار محصول دکارتی، حدس میزنم مشکلات ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let γ(G) be the domination number of a simple graph G and Gâ¡H be the Cartesian product of two simple graphs G and H. A function f:V(G)â{0,1,2} is a Roman dominating function (RDF) if for each vertex uâV0,NG(u)â©V2â â
, where Vi={uâV(G):f(u)=i}. The Roman domination number γR(G) is the minimum weight f(V(G))=âuâV(G)f(u) among all RDFs of G. Vizing conjectured in 1963 that γ(Gâ¡H)â¥Î³(G)γ(H) for any graphs G and H. To this day, this conjecture remains open. In this paper, we show that for each pair of simple graphs G and H, γ(Gâ¡H)â¥14γR(G)γR(H). This means that Vizing's conjecture holds for any pair of Roman graphs G and H. Moreover, we prove γR(Gâ¡H)â¥Î³(G)γ(H)+12minâ¡{γ(G),γ(H)} if G or H is nonempty, which is a slight improvement of γR(Gâ¡H)â¥Î³(G)γ(H) obtained by Wu in 2013 [22].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 135, July 2018, Pages 85-91
Journal: Information Processing Letters - Volume 135, July 2018, Pages 85-91
نویسندگان
Li-Dan Pei, Xiang-Feng Pan, Fu-Tao Hu,