Domination versus disjunctive domination in graphs

Michael A. Henning, Sinclair A. Marcon

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)261-273
Number of pages13
JournalQuaestiones Mathematicae
Volume39
Issue number2
DOIs
Publication statusPublished - 31 Mar 2016

Keywords

  • Domination
  • disjunctive domination

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Domination versus disjunctive domination in graphs'. Together they form a unique fingerprint.

Cite this