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

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

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