Characterizing minimal point set dominating sets. Issue 3 (1st December 2016)

• Record Type: Journal Article
• Authors: Gupta, Purnima; Singh, Rajesh; Arumugam, S.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 13:Issue 3(2016)
• Page Start: 283
• Page End: 289
• Publication Date: 2016-12-01
• Subjects: Domination -- Point-set domination -- Minimal point-set dominating set
• DOI: 10.1016/j.akcej.2016.07.003
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Dedicated to sweet memories of Dr. B.D Acharya A set D of vertices in a graph G = ( V, E ) is said to be a point-set dominating set (or, in short, psd-set) of G if for every subset S of V − D there exists a vertex v ∈ D such that the subgraph 〈 S ∪ { v } 〉 is connected; the set of all psd-sets of G will be denoted D p s ( G ) . The point-set domination number of a graph denoted by γ p ( G ) is the minimum cardinality of a psd-set of G . We obtain a lower bound for γ p ( G ) and characterize graphs which attain this bound. A psd-set D of a graph G is minimal if no proper subset of D is a psd-set of G . In this paper, we give a general characterization of psd-sets which are minimal. Also, in the case of separable graphs, we obtain more transparent and structure specific characterizations of minimal psd-sets.