کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776869 | 1413644 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A long-standing Vizing's conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, γ(Gâ¡H)â¥Î³(G)γ(H)â2, where γ stands for the domination number, and Gâ¡H is the Cartesian product of graphs G and H. In this note, we improve this bound by employing the 2-packing number Ï(G) of a graph G into the formula, asserting that γ(Gâ¡H)â¥(2γ(G)âÏ(G))γ(H)â3. The resulting bound is better than that of Clark and Suen whenever G is a graph with Ï(G)<γ(G)â2, and in the case G has diameter 2 reads as γ(Gâ¡H)â¥(2γ(G)â1)γ(H)â3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 10, October 2017, Pages 2398-2401
Journal: Discrete Mathematics - Volume 340, Issue 10, October 2017, Pages 2398-2401
نویسندگان
Boštjan Brešar,