Abstract
Abstract: For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.
Original language | English |
---|---|
Pages (from-to) | 547-561 |
Number of pages | 15 |
Journal | Quaestiones Mathematicae |
Volume | 37 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Keywords
- Graph
- algorithms
- distance
- domination
ASJC Scopus subject areas
- Mathematics (miscellaneous)