论文部分内容阅读
设G=(V，E)是一个不含孤立点的图，S()V(G).如果对于任意的顶点υ∈V(G)，均有|NG(υ)∩S|≥1，则称S是G的一个全控制集(简称TDS)，图G的所有全控制集中包含顶点数最少的全控制集称为G的最小全控制集，最小全控制集所包含的顶点数目称为G的全控制数，记为γt(G)，即γt(G)=min{|S|：S为G的全控制集}.顶点数等于γt(G)的全控制集称为γt(G)-集.图G=(V，E)称为广义θ-图，如果G是一个简单连通图并且它的两个端点x和y被至少两条内部不相交的路连接，使得对于任意的υ∈V＼{x，y}都有d(υ)=2.称G=Lm×n=(V，E)为m×n梯子图，其中m，n≥3，且m，n∈Z，如果G是由两条路u1u2...um和υ1υ2...υm通过对于每一个i∈Im添加一条具有n-1条边的路来连接ui和υi，使得对于每一个υ∈V＼{ui，υi：i∈Im)都满足d(υ)=2的简单连通图.在本文中，我们确定了广义θ-图的全控制数和m×n梯子图的全控制数，并给出了详细的证明过程。