论文部分内容阅读
设G=(V,E)是图，D是的V子集．若不在D中的每个点都至少和D中一点相邻，则称D为G的控制集，对于不含孤立点的图G，若控制集D中的每个点也至少和D中其它一点相邻，则称D为G的全控制集，最小（全）控制集所含的点数称为G的（全）控制数．非空（不含孤立点）图G的（全）约束数，记为b(G)(bt(G))，是指去掉G中最小边集的数目使得（全）控制数增加．G的（全）加强数是指添加最小边集的数目使得（全）控制数减小．
图G上的罗马控制函数是指，f:V→{0，1,2}，使得每一个值为0的点υ至少存在一个值为2的邻点u．f(V)=∑υ∈Vf(u)称为罗马控制函数f的权．最小罗马控制函数的权称为G的罗马控制数，记为γR(G).设G是一最大度点至少为2的图，它的罗马约束数，记为bR(G)，是指最少边集E’(C)E(G)的数目使得γR(G-E’)＞γR(G).
本文主要研究了图的约束数问题．首先证明了求一般图的（全）约束数和（全）加强数对应的判定问题都是NP-难的．
其次，本文考虑了格图的约束数和全约束数，得到了下面的结果，其中Gn，m=Pn×Pm是两条路Pn和Pm的笛卡尔乘积，A={1,2,3,5,6，9}.
b(G2,2)=3，b(G3,2)=2；
b(Gn,2)={1如果n是奇数，2如果n是偶数，n≥4；
b(Gn,3)={1如果n≡1,2(mod4),2如果n≡0,3(mod4),n≥3；
b(G5,4)=b(G9,4)=3,b(G6,4)=2,和对n（∈）A有b(Gn,4)=1；
bt(Gn,2)={1如果n≡0(mod3)，2如果n≡2(mod3),3如果n≡1(mod3)；
bt(Gn,3)=1;bt(G6,4)=2,和bt(G,4){=1如果n≡1(mod5)且n≠6，=2如果n≡4(mod5),≤3如果n≡2(mod5),≤4如果n≡0,3(mod5).同时，对阶数为n的(n-3)-正则图G得到了b(G)=n-3．
最后，讨论了图的罗马约束数问题，证明了求二部图的罗马约束数对应的判定问题是NP-难的，给出了罗马约束数的一些上下界，确定了完全t-部图和阶数为n的(n-3)-正则图罗马约束数的精确值．