亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        Cn×P2的符號全控制數(shù)與符號全加強數(shù)

        2019-06-09 02:25:30李寧范英梅
        廣西大學學報(自然科學版) 2019年6期
        關(guān)鍵詞:矛盾符號定義

        李寧,范英梅

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

        0 引言

        自從ZELINKA[1]提出符號全控制數(shù)(signed total domination number)的概念以來,已經(jīng)有很多學者對符號全控制數(shù)給出了深入的研究[2-5]。令G=(V(G),E(G))是一個無孤立點的簡單無向圖,其頂點集和邊集分別用V(G)和E(G)表示。定義圖G中的任意一個頂點v∈V(G)的開鄰集為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-正則的。對于任意S?V(G),NG(S)=∪v∈SNG(v),NG[S]=NG(S)∪S。對圖G的任意兩個子集A,B?V(G), 定義E(A,B) = {e=xy|x∈A,y∈B}、e(A,B) = |E(A,B)|。

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

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

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

        引理2r-正則圖G的階n≥3,則當r為奇數(shù)時γst(G)≥n/r;當r為偶數(shù)時γst(G)≥2n/r[5]。

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

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

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

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

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

        性質(zhì)1對任一頂點v,均成立|N(v)∩M|≤1。

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

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

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

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

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

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

        證明令函數(shù)f和函數(shù)g分別數(shù)圖G+A和圖G的最小符號控制函數(shù), 并且分別記f-1(a)和g-1(a)為值a在函數(shù)f和函數(shù)g下的原像。因為γst(G+A)<γst(G),所以|f-1(1)|≤|g-1(1)|-1。 也就是說|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)外層點集,顯然它們各自構(gòu)成一個長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上定義一個函數(shù)f:當x∈{v1,v2,u4,u6,…v6k-5,v6k-4,u6k-2,u6k-1,v6k+1,v6k+2,u6k+4}時,f(x)=-1;否則f(x)=1。易驗證對于任意一頂點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的頂點集上定義一個函數(shù)f如下:當x∈{v1,u1,v4,u4,…v6k-5,u6k-5,v6k-2,u6k-2}時f(x)=-1,其余情況下f(x)=1。易驗證對于任意一頂點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。

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

        2 Cn×P2 的符號全加強數(shù)

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

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

        反證假設存在不同的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)的一個最小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無交點,則δ(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。因為γst(Cn×P2+e1+e2)=2n-2|M|是偶數(shù),所以γst(Cn×P2+e1+e2)≥2k+2。矛盾。

        情形2若e1和e2有一個公共交點,本文記為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個在M中,本文僅需考慮兩類:

        若x,y∈M且z∈P(由對稱性,和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個在M中。由對稱性,本文僅需考慮以下兩種情況

        若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(由對稱性,和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。矛盾。

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

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

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

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

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

        反證假設存在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上的一個最小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可知:對于任一點v∈V(Cn×P2+e),為保證φ(N(v))≥1,必有|N[v]∩M|≤2。由性質(zhì)2可知中點或為孤立點,或為K2頂點。

        ① 若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中有一個點屬于M,則由對稱性我們可以令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。矛盾。

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

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

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

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

        反證假設存在不同的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無交點,則δ(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有一個公共交點,本文記為x,則令e1=xy,e2=xz。令φ是定義在G0上的一個最小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個在M中。由對稱性,可以考慮以下兩種情況:

        若x,y∈M且z∈P(與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≥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個在M中。由對稱性,可以考慮以下兩種情況:

        若y∈M且x,z∈P(與z∈M且x,y∈P對稱),則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。矛盾。

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

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

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

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

        反證假設存在不同的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上的一個最小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有一個交點,則:

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

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

        若|A∩M|=5,由對稱性討論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,由對稱性討論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。由對稱性,僅需討論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。由對稱性,僅需討論y,z∈M;a,y∈M;a,b∈M;x,y∈M;x,a∈M。易驗證,前三種時成立e(P,M)≤|P|-4+1+1+1+2≤4k和e(M,P)≥2(|M|-2)+3+3≥ 4k+4,矛盾。后兩個成立e(P,M)≤|P|-4+4×1≤4k-1和e(M,P)≥ 2(|M|-2)+4+3≥ 4k+5。矛盾。若|A∩M|=1。由對稱性,僅需討論x∈M;a∈M;y∈M。易驗證,第一種成立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。則對任意v∈V(G0),有|N[v]∩M|≤2。故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        ③ 兩條有一個公共交點,其余兩條邊各自獨立,可以記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也不成立。否則,對任意v∈V(G0),必有|N[v]∩M|≤2,故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        若|A∩M|=6,由對稱性知討論a∈P;d∈P;b∈P即可。前兩種時成立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。由對稱性僅需討論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,由對稱性僅需討論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后四種時成立e(P,M)≤ |P|-3+1+1+1≤4k-1和e(M,P)≥2(|M|-4)+3×4≥ 4k+6,矛盾。若|A∩M|=3。由對稱性僅需討論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,由對稱性僅需討論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,矛盾。其余時成立e(P,M)≤|P|-5+5×1≤4k-1和e(M,P)≥2(|M|-2)+3×2≥ 4k+4。矛盾。若|A∩M|=1,由對稱性僅需討論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個交點,則:

        ① 若三條交于2點,另一條獨立,可以記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也不成立,否則對任意v∈V(G0),有|N[v]∩M|≤2。故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        若|A∩M|=5,由對稱性僅需討論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,由對稱性僅需討論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。且前三種時e(P,M)≤|P|-2+1+1≤4k-1后三種時e(P,M)≤|P|-2+1+1≤4k,其余成立e(P,M)≤|P|-2+2+2≤4k+1,均矛盾。若|A∩M|=3。由對稱性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。前兩種時e(P,M)≤|P|-2+2+2≤4k+1;后2種時e(P,M)≤|P|-3+1+1+1≤4k-1;其余時e(P,M)≤|P|-3+1+2+1≤4k。均矛盾。若|A∩M|=2。由對稱性僅需討論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):前三種時e(P,M)≤|P|-4+1+2+2+1≤4k+1;后1種時e(P,M)≤ |P|-4+1×4≤4k-1;其余成立e(P,M)≤ |P|-4+1+2+1+1≤4k。均矛盾。若|A∩M|=1,由對稱性僅需討論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點,可以記e1=ab,e2=bc,e3=fg,e4=gh。令A={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也不成立。否則,對任意v∈V(G0),必有|N[v]∩M|≤2,故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        若|A∩M|=5,由對稱性僅需討論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,由對稱性僅需討論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,由對稱性僅需討論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,由對稱性討論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。由對稱性僅需討論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個交點。

        ① 4條邊依次相連??梢杂沞1=ab,e2=bc,e3=cd,e4=df。令A={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也不成立,否則對任意v∈V(G0),必有|N[v]∩M|≤2。故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        若|A∩M|=4,由對稱性僅需討論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,由對稱性僅需討論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。由對稱性僅需討論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,由對稱性僅需討論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條邊獨立??梢杂沞1=ab,e2=bc,e3=ca,e4=df。記A={a,b,c,d,f}。重復4.1的情形,可得A?M和A?P均不成立。

        若|A∩M|=4,由對稱性僅需討論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。由對稱性僅需討論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,由對稱性僅需討論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,由對稱性僅需討論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個交點,則可以記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也不成立,否則對任意v∈V(G0),必有|N[v]∩M|≤2。故|M|≤2×3k/3=2k,矛盾于|M|≥2k+1。

        若|A∩M|=3,由對稱性可知,僅需討論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。由對稱性知,僅需討論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,由對稱性僅需討論x∈M。此時,e(P,M)≤|P|-3+2×3≤4k+2,e(M,P)≥ 2(|M|-1)+3≥ 4k+3。矛盾。

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

        綜上,本文可以得到以下Cn×P2的符號全加強數(shù)的結(jié)論:

        猜你喜歡
        矛盾符號定義
        咯咯雞和嘎嘎鴨的矛盾
        幾類樹的無矛盾點連通數(shù)
        再婚后出現(xiàn)矛盾,我該怎么辦?
        中老年保健(2021年2期)2021-08-22 07:29:58
        學符號,比多少
        幼兒園(2021年6期)2021-07-28 07:42:14
        對矛盾說不
        童話世界(2020年13期)2020-06-15 11:54:50
        “+”“-”符號的由來
        變符號
        成功的定義
        山東青年(2016年1期)2016-02-28 14:25:25
        圖的有效符號邊控制數(shù)
        修辭學的重大定義
        當代修辭學(2014年3期)2014-01-21 02:30:44
        亚洲国产精品嫩草影院久久av| 国产亚洲视频在线观看网址| 久久久久久久98亚洲精品| 国产精品制服| h在线国产| 亚洲综合久久久中文字幕| 中文字幕第一页人妻丝袜| 国产人妻熟女高跟丝袜| 丰满少妇a级毛片野外| 波多野结衣一区| 精品少妇人妻久久免费| 在线播放草猛免费视频| 久久久精品一区aaa片| 日韩视频第二页| 少妇特殊按摩高潮不断| 亚洲最大中文字幕在线| 东北女人毛多水多牲交视频| 一级二级中文字幕在线视频| 亚州韩国日本区一区二区片| 少妇激情一区二区三区99| 性色av无码中文av有码vr| 午夜婷婷国产麻豆精品| 日本女优中文字幕四季视频网站| 亚洲成人中文字幕在线视频| 一本一道av中文字幕无码| 久久久久亚洲AV无码专区喷| 日本一区二区在线播放| 熟女无套高潮内谢吼叫免费| 国产精品福利自产拍久久| 国产精品欧美亚洲韩国日本| 国产精品一区二区三区四区亚洲| 国产精品特级毛片一区二区三区| 国产黄页网站在线观看免费视频| 激情五月天俺也去综合网| 日本一级特黄aa大片| 日韩av精品国产av精品| 国产高清国内精品福利99久久| 日韩人妖干女同二区三区| 把女的下面扒开添视频| 日韩欧美区| 日本高清色一区二区三区|