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