图的集控制数

Set Domination Number of Graphs

设图 G=(V,E).一子集 D■V,若对每一个 X■V-D,都存在一个非空子集合Y■D,使得由 X∪Y所导出的子图<X∪Y>连通,则称 D 为 G 的一个集控制集(sd-集).G 的集控制数γ.(G)是 G 的一个集控制集的最小基数.本文给出了集控制集的一个充要条件,并讨论了生成子图与补图的集控制数.

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,and there exists a nonempty set Y■D,such that the subgraph<XUY>induced by X∪Y is connected.The set-domintation number γ_s(G)of G is the minimum cardinality of a sd-set.In this paper a necessary and sufficient condition of a set-dominating set is given,and the set-domina- tion number of its spanning subgraph and complement is discussed.