Characterizing minimal point set dominating sets

摘要

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.