论文部分内容阅读
设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梯子图的全控制数,并给出了详细的证明过程。