Cn×P2的符號(hào)全控制數(shù)與符號(hào)全加強(qiáng)數(shù)

李寧,范英梅

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西南寧530004)

0 引言

自從ZELINKA[1]提出符號(hào)全控制數(shù)(signed total domination number)的概念以來(lái)，已經(jīng)有很多學(xué)者對(duì)符號(hào)全控制數(shù)給出了深入的研究[2-5]。令G=(V(G),E(G))是一個(gè)無(wú)孤立點(diǎn)的簡(jiǎn)單無(wú)向圖，其頂點(diǎn)集和邊集分別用V(G)和E(G)表示。定義圖G中的任意一個(gè)頂點(diǎn)v∈V(G)的開(kāi)鄰集為NG(v) = {u∈V(G)|uv∈E(G)}，閉鄰集為NG[v]=NG(v)∪{v}。頂v∈V(G)的度為dG(v)=|NG(v)|，最大度為Δ(G)=max{dG(v)|v∈V(G)}，最小度為δ(G)=min{dG(v)|v∈V(G)}。如果Δ(G)=δ(G)=r，則稱G是r-正則的。對(duì)于任意S?V(G)，NG(S)=∪v∈SNG(v)，NG[S]=NG(S)∪S。對(duì)圖G的任意兩個(gè)子集A,B?V(G), 定義E(A,B) = {e=xy|x∈A,y∈B}、e(A,B) = |E(A,B)|。

無(wú)向圖G= (V,E)，f:V→R是定義在頂點(diǎn)集V(G)上的實(shí)函數(shù)。f的權(quán)重定義為ω(f)=∑v∈Vf(v)。對(duì)于頂點(diǎn)集的任意一個(gè)子集S?V，定義f(S)=∑v∈Sf(v)，那么，ω(f) =f(V) 。如果函數(shù)f:V(G)→{-1,1}可以讓圖G上任意頂點(diǎn)v∈V滿足f(N(v))≥1，那么本文稱這個(gè)函數(shù)f是定義在V(G)上的符號(hào)全控制函數(shù) (signed total dominating function, STDF)。圖G的符號(hào)全控制數(shù)定義為γst(G)=min{ω(f)|f是圖G的一個(gè)STDF}。

作為研究圖的穩(wěn)定性的一個(gè)重要參數(shù)，圖G的加強(qiáng)數(shù)是由 KOK等[6]首次提出來(lái)的, 并且得到了很多很好的結(jié)論。在文獻(xiàn)[7]中，給出了圖G的符號(hào)全加強(qiáng)數(shù)(signed total reinforcement number)的定義：對(duì)于Ec(G)中的任意一子集S, 使得不等式γst(G+S) <γst(G)成立的最小的集合S的勢(shì)。使得γst(G+S)<γst(G)成立的最小的邊集合S成為圖G的符號(hào)全加強(qiáng)數(shù)集(signed total reinforcement set)。對(duì)符號(hào)全控制數(shù)和符號(hào)全加強(qiáng)數(shù)，學(xué)者們已經(jīng)給出了很多成果[5,8-10]：

引理1定義在圖G的頂點(diǎn)集上的符號(hào)全控制函數(shù)f是極小的當(dāng)且僅當(dāng)對(duì)于頂點(diǎn)集上的任意一個(gè)滿足f(v) = 1的頂點(diǎn)v∈V，均存在u∈N(v)，使得f[u]=f(N[u])∈{1,2}[5]。

引理2r-正則圖G的階n≥3，則當(dāng)r為奇數(shù)時(shí)γst(G)≥n/r；當(dāng)r為偶數(shù)時(shí)γst(G)≥2n/r[5]。

引理3階為n的圖G，其最小度δ≥2，則[5]:

對(duì)于任意兩個(gè)無(wú)孤立點(diǎn)的無(wú)向圖G和H，它們的乘積圖是以V(G)×V(H) 作為頂點(diǎn)集。兩個(gè)頂點(diǎn)(u1,v1)和(u2,v2)之間若存在一條邊當(dāng)且僅當(dāng)u1=u2且v1v2∈E(H)成立，或者v1=v2且u1u2∈E(G)成立。記G和H的乘積圖為G×H。

本文給出Cn×P2(n≥3)符號(hào)全控制數(shù)和符號(hào)全加強(qiáng)數(shù)。以下章節(jié)中，下標(biāo)中的加減運(yùn)算均使用mod(n)運(yùn)算規(guī)則。

1 Cn×P2 的符號(hào)全控制數(shù)

令f是定義在Cn×P2上的一個(gè)最小STDF且記P=f-1(1)、M=f-1(-1)。由Cn×P2是3-正則圖知：

性質(zhì)1對(duì)任一頂點(diǎn)v，均成立|N(v)∩M|≤1。

證明本文記|N(v)∩M|=N-,|N(v)∩P|=N+，則由符號(hào)全控制數(shù)的定義可得：1≤f(N(v)) =N+-N-=deg(v)-2N-=3-2N-。因此N-≤1，故結(jié)論成立。

性質(zhì)2Cn×P2中是由孤立點(diǎn)和K2組成。

證明由性質(zhì)1可知：則對(duì)任一M集中的點(diǎn)v，均成立|N(v)∩M|≤1。故結(jié)論成立。

性質(zhì)3如果存在M中的一個(gè)點(diǎn)v使得N(v)∩M=φ，則{u∈V|d(u,v)=1或2}?P。

證明對(duì)任意w∈{u∈V|d(u,v)=1或2}，如果d(w,v)=1，則由N(v)∩M=Φ可知，w∈P。如果d(w,v)=2且f(w)=-1，則對(duì)于N(v)和N(w)的公共交點(diǎn)x，成立f(N(x))≤f(w)+f(v)+1<0。矛盾。故假設(shè)不成立，所以w∈P，結(jié)論成立。

性質(zhì)4對(duì)于任意無(wú)孤立點(diǎn)的無(wú)向圖G，如果存在圖G的補(bǔ)圖的子集A，使得不等式γst(G+A)<γst(G)成立，那么γst(G+A)≤γst(G)-2。

證明令函數(shù)f和函數(shù)g分別數(shù)圖G+A和圖G的最小符號(hào)控制函數(shù), 并且分別記f-1(a)和g-1(a)為值a在函數(shù)f和函數(shù)g下的原像。因?yàn)棣胹t(G+A)<γst(G)，所以|f-1(1)|≤|g-1(1)|-1。 也就是說(shuō)|f-1(-1)|≥|g-1(-1)|+1。因此：γst(G+A)=|f-1(1)|-|f-1(-1)|≤|g-1(1)|-|g-1(-1)|-2=γst(G)-2。

證明由定義知Cn×P2就是Petersen圖P(n,1)，故可令U= {u1,u2,…,un}和V={v1,v2,…,vn}是它的內(nèi)外層點(diǎn)集，顯然它們各自構(gòu)成一個(gè)長(zhǎng)n的圈。

情形1n=3k(k∈N+)或n=3k+1(k∈N+)。

由Cn×P2是3-正則圖及引理2可知，γst(Cn×P2)≥|V(Cn×P2)|/3=2n/3。

情形2n=6k+5(k∈N)。

在Cn×P2上定義一個(gè)函數(shù)f：當(dāng)x∈{v1,v2,u4,u6,…v6k-5,v6k-4,u6k-2,u6k-1,v6k+1,v6k+2,u6k+4}時(shí)，f(x)=-1；否則f(x)=1。易驗(yàn)證對(duì)于任意一頂點(diǎn)x，均成立f(N(x))≥1。所以f是定義在Cn×P2上的STDF且γst(Cn×P2)≤f(V(Cn×P2))=4k+4。

情形3n=6k+2(k∈N+)。

在Cn×P2的頂點(diǎn)集上定義一個(gè)函數(shù)f如下：當(dāng)x∈{v1,u1,v4,u4,…v6k-5,u6k-5,v6k-2,u6k-2}時(shí)f(x)=-1，其余情況下f(x)=1。易驗(yàn)證對(duì)于任意一頂點(diǎn)x，均成立f(N(x))≥1。所以f是定義在Cn×P2上的STDF且γst(Cn×P2)≤f(V(Cn×P2))=4k+4。

由Cn×P2是3-正則圖及引理2知，γst(Cn×P2)≥|V(Cn×P2)|/3=4k+1+1/3。因此，4k+4≥γst(Cn×P2)≥4k+2。同理情形 1，可以斷言γst(Cn×P2)是偶數(shù)，所以γst(Cn×P2)= 4k+2或者4k+4。

假設(shè)γst(Cn×P2)= 4k+2。令g是定義在C6k+2×P2上的一個(gè)最小STDF且記P=g-1(1)、M=g-1(-1)，則由γst(Cn×P2)= 2n-2|M|可得|M|=4k+1。

2 Cn×P2 的符號(hào)全加強(qiáng)數(shù)

引理4若n=3k+1(k∈N+)，則Rst(Cn×P2)=3。

證明記G′=Cn×P2+vnvn-2+vnun-1+vn-2un-1，則在G′上定義一個(gè)函數(shù)g如下：當(dāng)x∈{v1,u1,…v3k-2,u3k-2,v3k}時(shí)g(x)=-1，其余情況下g(x)=1。易驗(yàn)證g是定義在G′上的STDF且γst(G′)≤g(V(G′))=2k<2k+2=γst(Cn×P2)。故Rst(Cn×P2)≤3。本文只需證明Rst(Cn×P2)≥3即可得到結(jié)論。

反證假設(shè)存在不同的e1,e2∈Ec(Cn×P2)(記G′=Cn×P2+e1+e2)使得γst(G′)<γst(Cn×P2)。由性質(zhì)4知γst(G′)≤2k。令φ是定義在V(Cn×P2+e1+e2)的一個(gè)最小STDF且記P=φ-1(1)、M=φ-1(-1)，則由γst(G′)=ω(φ)=|P|-|M|≤2k及|P|+|M|=2(3k+1)可得：|P|≤4k+1，|M|≥2k+1。

情形1若e1和e2無(wú)交點(diǎn)，則δ(Cn×P2+e1+e2)=3且Δ(Cn×P2+e1+e2)=4，由引理3可知γst(Cn×P2+e1+e2)≥2(3k+1)/3=2k+2/3。所以γst(Cn×P2+e1+e2)≥2k+1。因?yàn)棣胹t(Cn×P2+e1+e2)=2n-2|M|是偶數(shù)，所以γst(Cn×P2+e1+e2)≥2k+2。矛盾。

情形2若e1和e2有一個(gè)公共交點(diǎn),本文記為x，則可以令e1=xy,e2=xz。

①x,y,z∈M，則e(M,P)≥2(|M|-3)+e(x,P)+e(y,P)+e(z,P)≥2(|M|-3)+3+3+3= 2|M|+3≥ 4k+5；e(P,M)≤|P|≤4k+1。矛盾。

②x,y,z中有且僅有2個(gè)在M中，本文僅需考慮兩類：

若x，y∈M且z∈P(由對(duì)稱性,和x，z∈M且y∈P一樣)，則e(M,P)≥2(|M|-2)+e(x,P) +e(y,P)≥2(|M|-2)+3+3=2|M|+2≥4k+4；e(P,M)≤|P|≤4k+1。矛盾。

若y，z∈M且x∈P,則e(M,P)≥2(|M|-2)+e(y,P)+e(z,P)≥2(|M|-2)+3+3=2|M|+2≥4k+4；e(P,M)≤(|P|-1)+e(x,M)=(|P|-1)+2≤4k+2。矛盾。

③x,y,z中有且僅有1個(gè)在M中。由對(duì)稱性，本文僅需考慮以下兩種情況

若x∈M且y,z∈P，則e(M,P)≥2(|M|-1)+e(x,P)≥2(|M|-1)+3=2|M|+1≥4k+3；e(P,M)≤ (|P|-2)+e(y,M)+e(z,M)≤|P|-2+1+1=|P|≤4k+1。矛盾。

若y∈M且x,z∈P(由對(duì)稱性,和z∈M且x,y∈P一樣)，則e(M,P)≥2(|M|-1)+e(y,P)≥2(|M|-1)+3=2|M|+1≥4k+3；e(P,M)≤(|P|-2)+e(x,M)+e(z,M)≤|P|-2+2+1=|P|+1≤4k+2。矛盾。

綜上所示，假設(shè)不成立。故結(jié)論成立。

證明 情形1若k為偶數(shù)，則本文可以令n=6t+2。

此時(shí)γst(Cn×P2)=4t+4。記G′=Cn×P2+vnvn-2+vnun-1，則在G′上定義一個(gè)函數(shù)φ如下：

下面來(lái)著重說(shuō)一下我的這幅《樂(lè)園》的具體創(chuàng)作過(guò)程，主要包括構(gòu)圖、色彩、線條、肌理效果、展出方式。這幅作品的尺寸為100cm*200cm，采用的是毛氈材料拼貼的方式。

易驗(yàn)證對(duì)φ是定義在G′上的STDF且γst(G′)≤φ(V(G′))=4k+2<4k+4=γst(Cn×P2)。故Rst(Cn×P2)≤2。本文僅需證明Rst(Cn×P2)≥2即可得結(jié)論。

反證假設(shè)存在e∈Ec(Cn×P2)使得γst(Cn×P2+e) <γst(Cn×P2)= 4t+4，則由性質(zhì)4可知γst(Cn×P2+e)≤4t+2。

由引理3及δ(Cn×P2+e)=3<4=Δ(Cn×P2+e)可得γst(Cn×P2+e)≥2(6t+2)/3=4t+1+1/3，也即γst(Cn×P2+e)≥4t+2，所以γst(Cn×P2+e)=4t+2。令φ是定義在Cn×P2+e上的一個(gè)最小STDF且記P=φ-1(1)、M=φ-1(-1)，則由γst(Cn×P2+e)=ω(φ)=|P|-|M|=4t+2及|P|+|M|=2(6t+2)可得：|P|=8t+3,|M|=4t+1。

記e=xy，則在Cn×P2+e中，由Δ(Cn×P2+e)=4可知：對(duì)于任一點(diǎn)v∈V(Cn×P2+e)，為保證φ(N(v))≥1，必有|N[v]∩M|≤2。由性質(zhì)2可知中點(diǎn)或?yàn)楣铝Ⅻc(diǎn)，或?yàn)镵2頂點(diǎn)。

① 若x,y∈M，則e(M,P)≥2(|M|-2)+e(x,P)+e(y,P)=2(|M|-2)+3+3=8t+4,e(P,M)≤|P|=8t+3。矛盾。

② 若x,y中有一個(gè)點(diǎn)屬于M，則由對(duì)稱性我們可以令x∈M且y∈P。

若x在中孤立，則e(M,P)≥2(|M|-1)+e(x,P)=2(|M|-1)+4=2|M|+2=8t+4；e(P,M)≤|P|≤8t+3。矛盾。

綜上所示，假設(shè)不成立。故結(jié)論成立。

情形2若k為奇數(shù)，令n=6t+5，則γst(Cn×P2)=4t+4。

記G′=Cn×P2+u1vn+u2vn+u1vn-1，則在G′上定義一個(gè)函數(shù)φ如下：

易驗(yàn)證φ是定義在G′上的STDF且γst(G′)≤φ(V(G′))=4k+2<4k+4=γst(Cn×P2)。故Rst(Cn×P2)≤3。現(xiàn)在僅需證明Rst(Cn×P2)≥3即可得結(jié)論。

反證假設(shè)存在不同的e1,e2∈Ec(Cn×P2)使得γst(Cn×P2+e1+e2)<γst(Cn×P2)=4t+4,記G0=Cn×P2+e1+e2,則由性質(zhì)4知γst(G0)≤4t+2。

若e1和e2無(wú)交點(diǎn)，則δ(G0)=3且Δ(G0)=4，由引理3可知γst(G0)≥2(6t+5)/3=4t+3+1/3,也即γst(G0)≥4t+4。矛盾于γst(G0)≤4t+2。

若e1和e2有一個(gè)公共交點(diǎn),本文記為x，則令e1=xy,e2=xz。令φ是定義在G0上的一個(gè)最小STDF且記P=φ-1(1)、M=φ-1(-1)，則由γst(G0)=ω(φ)=|P|-|M|≤4t+2及|P|+|M| =2(6t+5)可得：|P|≤8t+6,|M|≥4t+4。

①x,y,z∈M，則e(M,P)≥2(|M|-3)+e(x,P)+e(y,P)+e(z,P)≥2(|M|-3)+3+3+3= 2|M|+3≥ 8t+11；e(P,M)≤ |P|≤8t+6。矛盾。

②x,y,z中有且僅有2個(gè)在M中。由對(duì)稱性，可以考慮以下兩種情況：

若x,y∈M且z∈P(與x，z∈M且y∈P對(duì)稱)，則e(M,P)≥2(|M|-2) +e(x,P) +e(y,P)≥2(|M|-2) +3 +3 =2|M|+2≥8t+10且e(P,M)≤(|P|-1)+e(z,M)=|P|-1+1≤8t+6。矛盾。

若y,z∈M且x∈P，則e(M,P)≥2(|M|-2)+e(y,P)+e(z,P)≥2(|M|-2)+3+3=2|M|+2≥8t+10且e(P,M)≤(|P|-1)+e(x,M)=(|P|-1)+2≤8t+7。矛盾。

③x,y,z中有且僅有1個(gè)在M中。由對(duì)稱性，可以考慮以下兩種情況：

若y∈M且x,z∈P(與z∈M且x,y∈P對(duì)稱)，則e(M,P)≥2(|M|-1) +e(y,P)≥2(|M|-1) +3 =2|M|+1≥8t+9且e(P,M)≤(|P|-2)+e(x,M)+e(z,M)=|P|-2+2+1≤8t+7。矛盾。

若x∈M且y,z∈P，則e(M,P)≥2(|M|-1)+e(x,P)≥2(|M|-1)+3=2|M|+1≥8t+9且e(P,M)≤(|P|-2)+e(y,M)+e(z,M)=(|P|-2)+1+1≤8t+6。矛盾。

綜上所示，假設(shè)不成立。故結(jié)論成立。

引理6若n=3k(k≥2,k∈N+)，則Rst(Cn×P2)=5。

證明記G′=Cn×P2+v1u2+v1v3+v3vn-1+vn-1un+unu2，則在G′上定義函數(shù)φ：

易驗(yàn)證對(duì)φ是定義在G′上的STDF且γst(G′)≤φ(V(G′))=2k-2<2k=γst(Cn×P2)。故Rst(Cn×P2)≤5?，F(xiàn)在僅需證明Rst(Cn×P2)≥5即可得結(jié)論。

反證假設(shè)存在不同的e1,e2,e3,e4∈Ec(Cn×P2) (記G0=Cn×P2+e1+e2+e3+e4)使得γst(G0)<γst(Cn×P2)=2k，則由性質(zhì)4知γst(G0)≤2k-2。令φ是定義在G0上的一個(gè)最小STDF且記P=φ-1(1)、M=φ-1(-1)，則由γst(G0)=ω(φ)=|P|-|M|≤2k-2及|P|+|M|=2×3k可得：|P|≤4k-1，|M|≥2k+1。

情形1若e1,e2,e3,e4兩兩不交，則δ(G0)=3且Δ(G0)=4，由引理3可知γst(G0)≥2×3k/3=2k。矛盾于γst(G0)≤2k-2。

情形2若e1,e2,e3,e4有一個(gè)交點(diǎn),則：

①e1,e2,e3,e4有一個(gè)公共交點(diǎn),記為x，本文斷言x∈P。否則，由定義可知e(P,M)≤|P|≤4k-1；e(M,P)≥2(|M|-1)+4≥ 4k+4。矛盾。所以對(duì)于任意v∈V(G0)，必有|N[v]∩M|≤2。故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

② 若三條交于一點(diǎn)，一條獨(dú)立,則可記e1=xa,e2=xb,e3=xc,e4=yz。為保證f(N(x))≥1，則a,b,c中至少有一個(gè)點(diǎn)在P中。記A={x,y,z,a,b,c}，則|A∩M|≤5。

若|A∩M|=5，由對(duì)稱性討論a∈P即可。e(P,M)≤|P|-1+e(a,M)≤4k-1；e(M,P)≥2(|M|-5) +e(x,P)+e(b,P)+e(c,P)+e(y,P)+e(z,P)≥ 4k+8。矛盾。若|A∩M|=4，由對(duì)稱性討論c,z∈P;b,c∈P;x,c∈P即可。前兩者成立e(P,M)≤|P|-2+1+1≤4k-1和e(M,P)≥2(|M|-4)+4+3×3≥4k+7。x,c∈P成立e(P,M)≤|P|-2+2+1≤ 4k；e(M,P)≥2 (|M|-4) +3×4≥ 4k+6。矛盾。若|A∩M|=3。由對(duì)稱性，僅需討論x,a,b∈M;x,a,y∈M;x,y,z∈M;a,b,y∈M;a,y,z∈M。前三種情況均成立e(P,M)≤|P|-3+1+1+1≤4k-1和e(M,P)≥2(|M|-3)+4+3+3≥ 4k+6。矛盾。后二種情況均成立e(P,M)≤|P|-3+2+1+1≤4k；e(M,P)≥ 2(|M|-3)+3×3≥ 4k+5。矛盾。若|A∩M|=2。由對(duì)稱性，僅需討論y,z∈M;a,y∈M;a,b∈M;x,y∈M;x,a∈M。易驗(yàn)證，前三種時(shí)成立e(P,M)≤|P|-4+1+1+1+2≤4k和e(M,P)≥2(|M|-2)+3+3≥ 4k+4，矛盾。后兩個(gè)成立e(P,M)≤|P|-4+4×1≤4k-1和e(M,P)≥ 2(|M|-2)+4+3≥ 4k+5。矛盾。若|A∩M|=1。由對(duì)稱性，僅需討論x∈M;a∈M;y∈M。易驗(yàn)證，第一種成立e(P,M)≤|P|-5+1×5≤4k-1和e(M,P)≥2(|M|-1)+4≥4k+4，矛盾。后兩種成立e(P,M)≤ |P|-5+2+4×1≤4和e(M,P)≥ 2(|M|-1)+3≥ 4k+3，矛盾。若|A∩M|=0。則對(duì)任意v∈V(G0)，有|N[v]∩M|≤2。故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

③ 兩條有一個(gè)公共交點(diǎn),其余兩條邊各自獨(dú)立，可以記e1=ab,e2=bc,e3=df,e4=gh。記A={a,b,c,d,f,g,h}，則A?M不成立。否則，e(P,M)≤|P|≤4k-1和e(M,P)≥2(|M|-7)+3×7≥ 4k+9相矛盾，A?P也不成立。否則，對(duì)任意v∈V(G0)，必有|N[v]∩M|≤2，故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

若|A∩M|=6，由對(duì)稱性知討論a∈P;d∈P;b∈P即可。前兩種時(shí)成立e(P,M)≤ |P|-1+1≤ 4k-1和e(M,P)≥2(|M|-6)+3×6≥4k+8，矛盾。最后一種成立e(P,M)≤|P|-1+2≤4k和e(M,P)≥ 2(|M|-6) +3×6≥ 4k+8。矛盾。若|A∩M|=5。由對(duì)稱性僅需討論d,g∈P;a,c∈P;a,d∈P；d,f∈P;a,b∈P;b,d∈P即可。前四種情形下成立e(P,M)≤|P|-2+1+1≤4k-1和e(M,P)≥ 2(|M|-5) +3×5≥4k+7，矛盾。后兩種下成立e(P,M)≤ |P|-2+2+1≤4k和e(M,P)≥2(|M|-5)+3×5≥ 4k+7。矛盾。若|A∩M|=4，由對(duì)稱性僅需討論a,b,c∈P;a,b,d∈P;b,d,f∈P;b,d,g∈P;a,c,d∈P;a,d,f∈P;a,d,g∈P;d后四種時(shí)成立e(P,M)≤ |P|-3+1+1+1≤4k-1和e(M,P)≥2(|M|-4)+3×4≥ 4k+6，矛盾。若|A∩M|=3。由對(duì)稱性僅需討論a,b,c∈M;a,b,d∈M;b,d,f∈M；b,d,g∈M;a,c,d∈M;a,d,f∈M;a,d,g∈M;d,f,g∈M。前四種成立e(P,M)≤ |P|-4+1×4≤4k-1和e(M,P)≥2(|M|-3)+3×3≥ 4k+5，矛盾。后4種成立e(P,M)≤ |P|-4+1×3+2≤4k和e(M,P)≥2(|M|-3)+3×3≥ 4k+5,矛盾。若|A∩M|=2，由對(duì)稱性僅需討論d,g∈P;a,c∈P;a,d∈Pd,f∈P;a,b∈P;b,d∈P即可。前四種成立e(P,M)≤|P|-5+1×4+2≤4k和e(M,P)≥2(|M|-2)+3×2≥ 4k+4，矛盾。其余時(shí)成立e(P,M)≤|P|-5+5×1≤4k-1和e(M,P)≥2(|M|-2)+3×2≥ 4k+4。矛盾。若|A∩M|=1，由對(duì)稱性僅需討論a∈M;d∈M;b∈M。前2種成立e(P,M)≤|P|-6+1×5+2≤4k和e(M,P)≥ 2(|M|-1)+3×1≥4k+3，矛盾。其余成立e(P,M)≤ |P|-6+1×6≤4k-1和e(M,P)≥2(|M|-1)+3×1≥ 4k+3，矛盾。

情形 3若e1,e2,e3,e4有2個(gè)交點(diǎn),則：

① 若三條交于2點(diǎn)，另一條獨(dú)立，可以記e1=ab,e2=bc,e3=cd,e4=fg。記A={a,b,c,d,f,g}。則A?M不成立。否則，e(P,M)≤|P|≤4k-1且e(M,P)≥2(|M|-6)+3×6≥ 4k+8。矛盾。A?P也不成立，否則對(duì)任意v∈V(G0)，有|N[v]∩M|≤2。故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

若|A∩M|=5，由對(duì)稱性僅需討論a∈P;g∈P;b∈P即可。前2種成立e(P,M)≤|P-1+1≤4k-1和e(M,P)≥2(|M|-5)+3×5≥4k+7，矛盾。其余成立e(P,M)≤|P|-1+1≤4k-1和e(M,P)≥ 2(|M|-5)+3×5≥ 4k+7。矛盾。若|A∩M|=4，由對(duì)稱性僅需討論g,f∈P;d,f∈P;a,d∈P;b,c∈P;c,f∈P;c,d∈P;b,d∈P。均成立e(M,P)≥2(|M|-4)+3×4≥ 4k+6。且前三種時(shí)e(P,M)≤|P|-2+1+1≤4k-1后三種時(shí)e(P,M)≤|P|-2+1+1≤4k，其余成立e(P,M)≤|P|-2+2+2≤4k+1，均矛盾。若|A∩M|=3。由對(duì)稱性d,f,g∈M;a,d,f∈M;c,f,g∈M;d,f,c∈Mb,d,f∈M;a,c,d∈M;b,c,f∈M;b,c,d∈M。這些情況下均成立e(M,P)≥2(|M|-3)+3×3≥ 4k+5。前兩種時(shí)e(P,M)≤|P|-2+2+2≤4k+1；后2種時(shí)e(P,M)≤|P|-3+1+1+1≤4k-1；其余時(shí)e(P,M)≤|P|-3+1+2+1≤4k。均矛盾。若|A∩M|=2。由對(duì)稱性僅需討論g,f∈M;d,f∈M;a,d∈M;c,f∈M;c,d∈M;b,d∈M;b,c∈M即可。這些情況下均成立e(M,P)≥2(|M|-2)+3×2≥ 4k+4。討論e(P,M)：前三種時(shí)e(P,M)≤|P|-4+1+2+2+1≤4k+1；后1種時(shí)e(P,M)≤ |P|-4+1×4≤4k-1；其余成立e(P,M)≤ |P|-4+1+2+1+1≤4k。均矛盾。若|A∩M|=1，由對(duì)稱性僅需討論a∈M;g∈M;b∈M即可。前兩種有e(P,M)≤|P|-5+1×3+2×2≤4k+1和e(M,P)≥2(|M|-1)+3≥ 4k+3，矛盾。其余成立e(P,M)≤|P|-5+ 1×4+5≤4k和e(M,P)≥2(|M|-1)+3≥ 4k+3，矛盾。

② 若兩條邊交于1點(diǎn)，可以記e1=ab,e2=bc,e3=fg,e4=gh。令A(yù)={a,b,c,f,g,h}，則A?M不成立。否則e(P,M)≤|P|≤4k-1和e(M,P)≥2(|M|-6)+3×6≥ 4k+8相矛盾，A?P也不成立。否則，對(duì)任意v∈V(G0)，必有|N[v]∩M|≤2，故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

若|A∩M|=5，由對(duì)稱性僅需討論a∈P和b∈P。二者均成立e(M,P)≥ (|M|-5) +3×5≥ 4k+7。前者有e(P,M)≤|P|-1+1≤4k-1，后者有e(P,M)≤ |P|-1+2≤4k。均矛盾。若|A∩M|=4，由對(duì)稱性僅需討論a,b∈P;a,g∈P;②a,c∈P;③a,f∈P;b,g∈P。均成立e(M,P)≥2(|M|-4)+3×4≥4k+6。且前2種有e(P,M)≤|P|-2+1+2≤4k；后1種有e(P,M)≤ |P|-2+1+1≤4k-1；其余成立e(P,M)≤ |P|-2+2+2≤4k+1。均矛盾。若|A∩M|=3，由對(duì)稱性僅需討論a,b,c∈M;a,b,f∈M;a,c,g∈M;a,b,g∈M;a,c,f∈M。這些情況下均成立e(M,P)≥2(|M|-3)+3×3≥ 4k+5。且前3種有e(P,M)≤|P|-3+1+2+1≤4k；后1種有e(P,M)≤ |P|-3+2+2+1≤4k+1；其余成立e(P,M)≤|P|-3+1×3≤4k-1。均矛盾。若|A∩M|=2，由對(duì)稱性討論a,b∈M;a,g∈M;b,g∈M;a,c∈M;a,f∈M。這些情況下均成立e(M,P)≥2(|M|-2)+3×2≥ 4k+4。討論e(P,M)：前2種有e(P,M)≤|P|-4+1×3+2≤4k；后2種有e(P,M)≤ |P|-4+2×2+1×2≤4k+1；其余成立e(P,M)≤ |P|-4+1×4≤4k-1。均矛盾。若|A∩M|=1。由對(duì)稱性僅需討論a∈M和b∈M。均成立e(M,P)≥2(|M|-1)+3≥4k+3。且前者有e(P,M)≤|P|-5+1×3+2×2≤4k+1，后者有e(P,M)≤ |P|-5+1×4+2≤4k。均矛盾。

情形4若e1,e2,e3,e4有3個(gè)交點(diǎn)。

① 4條邊依次相連?？梢杂沞1=ab,e2=bc,e3=cd,e4=df。令A(yù)={a,b,c,d,f}。則A?M不成立。否則e(P,M)≤|P|≤4k-1和e(M,P)≥2(|M|-5)+3×5≥ 4k+7相矛盾。A?P也不成立，否則對(duì)任意v∈V(G0)，必有|N[v]∩M|≤2。故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

若|A∩M|=4，由對(duì)稱性僅需討論a∈P;b∈P;c∈P即可。均成立e(M,P)≥2(|M|-4)+3×4≥ 4k+6。且前1種有e(P,M)≤|P|-1+1≤4k-1；其余成立e(P,M)≤ |P|-1+2≤4k。均矛盾。若|A∩M|=3，由對(duì)稱性僅需討論d,f∈P;c,f∈P;a,f∈P;c,d∈P;b,d∈P。均成立e(M,P)≥2(|M|-3)+3×3≥ 4k+5。且前3種有e(P,M)≤|P|-2+1+2≤4k；后2種有e(P,M)≤|P|-2+2+2≤4k+1；其余成立e(P,M)≤ |P|-2+1+1≤4k-1。均矛盾。若|A∩M|=2。由對(duì)稱性僅需討論d,f∈M;c,f∈M;a,d∈M;a,f∈M;c,d∈M;b,d∈M即可。這些情況下均成立e(M,P)≥2(|M|-2)+3×2≥ 4k+4。討論e(P,M)：前3種有e(P,M)≤|P|-3+1+2+2≤4k+1；后2種有e(P,M)≤|P|-3+1+2+1≤4k；其余成立e(P,M)≤ |P|-3+3×2≤4k+2。均矛盾。若|A∩M|=1，由對(duì)稱性僅需討論b∈M;c∈M;a∈M。前2種有e(P,M)≤|P|-4+1×2+2×2≤4k+1和e(M,P)≥2(|M|-1)+3≥ 4k+3，矛盾。其余有e(P,M)≤ |P|-4+2×3 +1≤4k+2和e(M,P)≥2(|M|-1)+3≥4k+3，矛盾。

② 若3條邊首尾相連，1條邊獨(dú)立?？梢杂沞1=ab,e2=bc,e3=ca,e4=df。記A={a,b,c,d,f}。重復(fù)4.1的情形，可得A?M和A?P均不成立。

若|A∩M|=4，由對(duì)稱性僅需討論a∈P;d∈P。均成立e(M,P)≥ 2(|M|-4)+3×4≥ 4k+6且前者成立e(P,M)≤|P|-1+2≤4k；后者成立e(P,M)≤|P|-1+1≤ 4k-1。均矛盾。若|A∩M|=3。由對(duì)稱性僅需討論a,b∈P;d,f∈P;a,d∈P。均成立e(M,P)≥2(|M|-3)+3×3≥4k+5。且第1種有e(P,M)≤ |P|-2+2+2≤4k+1；第2種有e(P,M)≤ |P|-2+1+1≤4k-1；其余成立e(P,M)≤ |P|-2+2+1≤4k。均矛盾。若|A∩M|=2，由對(duì)稱性僅需討論a,b∈M;d,f∈M;a,d∈M。均成立e(M,P)≥ 2(|M|-2) +3×2≥4k+4。且第1種有e(P,M)≤|P|-3+1+1+2≤4k；第2種有e(P,M)≤ |P|-3+2×3≤4k+2；其余成立e(P,M)≤ |P|-3+2+2+1≤4k+1。均矛盾。若|A∩M|=1，由對(duì)稱性僅需討論a∈M;d∈M。前者成立e(P,M)≤ |P|-4+2×2+1×2≤4k+1和e(M,P)≥2(|M|-1)+3≥ 4k+3，矛盾。后者成立e(P,M)≤ |P|-4+1+2×3≤4k+2和e(M,P)≥2(|M|-1)+3≥ 4k+3，矛盾。

情形5若e1,e2,e3,e4有4個(gè)交點(diǎn)，則可以記e1=xy,e2=yz,e3=zt,e4=tx。記A={x,y,z,t}。則A?M不成立。否則e(P,M)≤|P|≤4k-1和e(M,P)≥2(|M|-4)+3×4≥ 4k+6相矛盾。A?P也不成立，否則對(duì)任意v∈V(G0)，必有|N[v]∩M|≤2。故|M|≤2×3k/3=2k，矛盾于|M|≥2k+1。

若|A∩M|=3，由對(duì)稱性可知，僅需討論x,y,z∈M且t∈P。則e(M,P)≥2(|M|-3)+3×3≥ 4k+5，e(P,M)≤|P|-1+2≤4k。矛盾。若|A∩M|=2。由對(duì)稱性知，僅需討論x,y∈M;x,t∈M。均成立e(M,P)≥2(|M|-2)+3×2≥ 4k+4和e(P,M)≤|P|-2+2+2≤4k+1。矛盾。若|A∩M|=1，由對(duì)稱性僅需討論x∈M。此時(shí)，e(P,M)≤|P|-3+2×3≤4k+2,e(M,P)≥ 2(|M|-1)+3≥ 4k+3。矛盾。

綜上所示，假設(shè)不成立。故結(jié)論成立。

綜上，本文可以得到以下Cn×P2的符號(hào)全加強(qiáng)數(shù)的結(jié)論：