邻全控制数和连通控制数相等的树和单圈图的刻画

摘要

设图G=(V，E )是一个没有孤立点，阶为n的图. 如果S?V，VS 中的每一个点都与S 中的一些点相邻，那么 S是G的一个控制集. 如果 G [N (S)]中没有孤立点，那么G的一个控制集S 称为G的一个邻全控制集.G的所有邻全控制集中包含顶点数最少的那个数称为G的邻全控制数，记为γnt(G ).大小为γnt(G)的邻全控制集称为G的最小邻全控制集. 如 果 G[S]网是连通的，那 么 G的一个控制集S 称 为 G的一个连通控制集.G的所有极小连通控制集中包含顶点数最少的那个数称为G的连通控制数，记为γC(G ).本文中，第一，我们根据树的内点|I(T )|大小来对γnt(T)=γc (T)的树T的特征进行分类. 第二，借助我们研究出的γnt(T)=γc(T)的树T的特征分类.其次，我们由|X|的大小对γnt(G)=γc(G)的单圈图G的特征进行分类. 最后，根据 G [X] 上的最长路t的大小来对满足条件 |X|≤4的γnt(G)=γc(G)的单圈图G的特征再进行分类.

目录

第一个书签之前