Vertices contained in all or in no minimum disjunctive dominating set of a tree

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, γ(G), of G is the cardinality of a minimum dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, γ^d ₂(G), of G is the cardinality of a minimum disjunctive dominating set in G. In this paper, we characterize the vertices contained in all or in no minimum disjunctive dominating set of a tree. © 2017 Utilitas Mathematica Publishing Inc.. All rights reserved.