Domination versus disjunctive domination in graphs. Issue 2 (31st March 2016)

• Record Type: Journal Article
• Authors: Henning, Michael A.; Marcon, Sinclair A.
• Is Part Of: Quaestiones mathematicae. Volume 39:Issue 2(2016)
• Page Start: 261
• Page End: 273
• Publication Date: 2016-03-31
• Subjects: 05C69; Domination -- disjunctive domination; Mathematics -- Periodicals; 510.5
• DOI: 10.2989/16073606.2015.1068237
• Languages: English
• ISSNs: 1607-3606

Abstract

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.