Article ID Journal Published Year Pages File Type
8902812 AKCE International Journal of Graphs and Combinatorics 2016 7 Pages PDF
Abstract
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 Dps(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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,