کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4646734 1342311 2017 10 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Matchings, path covers and domination
ترجمه فارسی عنوان
تطابق‌ها، پوشش مسیر و سلطه
کلمات کلیدی
تطابق؛ پوشش مسیر؛ تسلط کل ؛ سلطه کل محله
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We show that if GG is a graph with minimum degree at least three, then γt(G)≤α′(G)+(pc(G)−1)∕2γt(G)≤α′(G)+(pc(G)−1)∕2 and this bound is tight, where γt(G)γt(G) is the total domination number of GG, α′(G)α′(G) the matching number of GG and pc(G)pc(G) the path covering number of GG which is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if GG is a connected graph on at least six vertices, then γnt(G)≤α′(G)+pc(G)∕2γnt(G)≤α′(G)+pc(G)∕2 and this bound is tight, where γnt(G)γnt(G) denotes the neighborhood total domination number of GG. We observe that every graph GG of order nn satisfies α′(G)+pc(G)∕2≥n∕2α′(G)+pc(G)∕2≥n∕2, and we characterize the trees achieving equality in this bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 1, 6 January 2017, Pages 3207–3216
نویسندگان
, ,