کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421121 684142 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Domination versus disjunctive domination in trees
ترجمه فارسی عنوان
سلطه در برابر سلطه دیوانه در درختان
کلمات کلیدی
تسلط، سلطه تفکیک، درختان
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A dominating set in a graph GG is a set SS of vertices of GG such that every vertex not in SS is adjacent to a vertex of SS. The domination number, γ(G)γ(G), of GG is the minimum cardinality of a dominating set of GG. A set SS of vertices in GG is a disjunctive dominating set in GG if every vertex not in SS is adjacent to a vertex of SS or has at least two vertices in SS at distance  22 from it in GG. The disjunctive domination number, γ2d(G), of GG is the minimum cardinality of a disjunctive dominating set in GG. It is known that there exist graphs GG that belong to the class of bipartite graphs or claw-free graphs or chordal graphs such that γ(G)>Cγ2d(G) for any given constant  CC. In this paper, we show that if TT is a tree, then γ(T)≤2γ2d(T)−1, and we provide a constructive characterization of the trees achieving equality in this bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 171–177
نویسندگان
, ,