Characterizing minimal point set dominating sets. Issue 3 (1st December 2016) - Gupta, Purnima; Singh, Rajesh; Arumugam, S.
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.