期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2016
卷号：13
期号：3
页码：283-289
DOI：10.1016/j.akcej.2016.07.003
语种：English
出版社：Elsevier
摘要：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 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.
关键词：KeywordsenDominationPoint-set dominationMinimal point-set dominating set
