کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421121 | 684142 | 2015 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 171–177