| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421121 | Discrete Applied Mathematics | 2015 | 7 Pages |
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.
