图的集控制数

设图Ｇ＝（Ｖ，Ｅ）．一子集Ｄ包含于Ｖ，若对每一个Ｘ包含于Ｖ－Ｄ，都存在一个非空子集合Ｙ包含于Ｄ，使得由Ｘ∪Ｙ所导出的子图（Ｘ∪Ｙ）连通，则称Ｄ为Ｇ的一个集控制集（ｓｄ－集）。Ｇ的集控制数ｙ２（Ｇ）是Ｇ的一个集控制集的最小基数。本文给出了集控制集一个充要条件，并讨论了生成子图与补图的集控制数。