Domination versus disjunctive domination in graphs. Issue 2 (31st March 2016) - Henning, Michael A.
Abstract: A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S . The domination number of G is the minimum cardinality of a dominating set of G . For a positive integer b, a set S of vertices in a graph G is a b -disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G . The b -disjunctive domination number of G is the minimum cardinality of a b -disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b -disjunctive dominating sets in a graph. A characterization of minimal b -disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b -disjunctive domination number for various families of graphs, including regular graphs and trees.