圖的約束數(shù)研究.pdf

1、設(shè)G=(V,E)是圖，D是的V子集．若不在D中的每個點都至少和D中一點相鄰，則稱D為G的控制集，對于不含孤立點的圖G，若控制集D中的每個點也至少和D中其它一點相鄰，則稱D為G的全控制集，最小（全）控制集所含的點數(shù)稱為G的（全）控制數(shù)．非空（不含孤立點）圖G的（全）約束數(shù)，記為b(G)(bt(G))，是指去掉G中最小邊集的數(shù)目使得（全）控制數(shù)增加．G的（全）加強(qiáng)數(shù)是指添加最小邊集的數(shù)目使得（全）控制數(shù)減?。?br>　　 圖G上的羅馬控制

2、函數(shù)是指，f:V→{0，1,2}，使得每一個值為0的點υ至少存在一個值為2的鄰點u．f(V)=∑υ∈Vf(u)稱為羅馬控制函數(shù)f的權(quán)．最小羅馬控制函數(shù)的權(quán)稱為G的羅馬控制數(shù)，記為γR(G).設(shè)G是一最大度點至少為2的圖，它的羅馬約束數(shù)，記為bR(G)，是指最少邊集E’(C)E(G)的數(shù)目使得γR(G-E’)＞γR(G).
　　 本文主要研究了圖的約束數(shù)問題．首先證明了求一般圖的（全）約束數(shù)和（全）加強(qiáng)數(shù)對應(yīng)的判定問題都是NP-難

3、的．
　　 其次，本文考慮了格圖的約束數(shù)和全約束數(shù)，得到了下面的結(jié)果，其中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是奇數(shù)，2如果n是偶數(shù)，n≥4；
　　 b(Gn,3)={1如果n≡1,2(mod4),2如果n≡0,3(mod4),n≥3；
　　 b(G5,4)=b(G9,

4、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).同時，對階數(shù)為n的(n-3)-正則圖G得到了b(G)=n-