关于集控制集的若干结论

Some Results about Set Dominating Set

设图Ｇ＝（Ｖ，Ｅ）．一子集ＤＶ，若对任何ＸＶ－Ｄ，都存在一个非空子集ＹＤ，使得导出子图〈Ｘ∪Ｙ〉连通，则称Ｄ为Ｇ的集控制集（ｓｄ－集）．Ｇ的集控制数γｓ（Ｇ）是Ｇ的集控制集的最小基数．基数为γｓ（Ｇ）的集控制集称为Ｇ的最小集控制集．本文讨论了割点属于Ｇ的任一最小集控制集的必要条件，并且给出了Ｇ有独立集控制集的充要条件．

Let G(V,E) be a graph.A set DV is a set dominating set(sd set)if for every set XV-D ,there exists a nonempty set YD ,such that the subgraph〈 X∪Y 〉induced by X∪Y is connected.The set domination number γ s( G )is the minimum cardinality of a sd set.In this paper,a necessary condition that a cut vertex belongs to every γ s set of G is discussed,and a necessary and sufficient condition of existing indepedent set dominating set in G is given.