The disjunctive domination number of a graph

Wayne Goddard, Michael A. Henning, Charles A. McPillan

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)


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 languageEnglish
Pages (from-to)547-561
Number of pages15
JournalQuaestiones Mathematicae
Issue number4
Publication statusPublished - 1 Jan 2014


  • Graph
  • algorithms
  • distance
  • domination

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'The disjunctive domination number of a graph'. Together they form a unique fingerprint.

Cite this