關(guān)于ng階2連通圖gc

關(guān)于ng階2連通圖gc

在這項(xiàng)工作中，研究的地圖是有限的，g是圖g的最小比例。假設(shè)u是g的點(diǎn)，v1是g的一個(gè)子圖，則ng1（u）=v，v（1g），u和n（u）可以簡(jiǎn)化為n（u）。nu）u，圖。g的長(zhǎng)度為m的圓圈由s表示。s：x1sxmx1，xmi和s（1）im，表示厘米上的點(diǎn)相同。n（u）=s。認(rèn)識(shí)四、五、七、二、南）cm（u）西-1cm（u），n（u）s，s（u）s（u）n（u）n（u），。圖G的鄰域并NC表示為:NC=min狖|N(x)∪N(y)|x,y∈V(G),xyE(G)狚.如果任一整數(shù)l(3≤l≤n),n階圖G均有長(zhǎng)為l的圈,則稱(chēng)G為泛圈圖.未定義符號(hào)見(jiàn)文獻(xiàn).2定理與證明1991年Faudree等人在文中得到結(jié)果:定理1n階2連通圖G,NC≥n-δ,則G是哈密頓圖.本文中進(jìn)一步得到:定理22連通n(n≥6)階圖G,若NC≥n-δ,則G是泛圈圖或此定理的證明要用到推廣了的數(shù)學(xué)歸納法,稱(chēng)為(雙)重?cái)?shù)學(xué)歸納法.即:某問(wèn)題對(duì)自然數(shù),+均具有性質(zhì),若假設(shè)對(duì)任意自然數(shù)n,n+1(n≥k)均具有性質(zhì)P的情況下,推出對(duì)n+2也具有性質(zhì)P,則此問(wèn)題對(duì)不小于k的任一自然數(shù)均具有性質(zhì)P.此種數(shù)學(xué)歸納法的正確性是顯然的,并可推廣到n種.引理1n(n≥6)階2連通圖G,NC≥n-δ,則G有C3,C4或證明現(xiàn)假設(shè)證明G有C3,C4.(1)δ=2,此時(shí)因n≥6,所以存在x∈V(G)滿足d(x)≥3.這是因?yàn)槿魎∈V(G),均有d(u)=2,又因G是2連通的,這就是G=Cn:x1x2xnx1,而NC≤|N(x1)∪N(x3)|≤|V(G)|-|狖x1,x3,x5狚|≤n-δ-1矛盾.這說(shuō)明存在x∈V(G)滿足d(x)≥3,這時(shí)N(x)中至少有相鄰的兩點(diǎn),否則記u,v∈N(x),則NC≤|N(u)∪N(v)|≤|V(G)|-|N(x)|≤n-δ矛盾.說(shuō)明N(x)中有相鄰的兩點(diǎn)(記為xi,xj),則有xxixjx就是C3.因G是2連通的,所以C3中至少有兩點(diǎn)(記為xi,xj)和G-C3中有點(diǎn)相鄰,此時(shí)則有a:(N(xi)V(C3))∩(N(xj)V(C3))≠,或b:x和(N(xi)V(C3))∪(N(xj)V(C3))中某點(diǎn)相鄰,或c:記u∈N(xi)V(C3),v∈N(xj)V(C3),有uv∈E(G).因?yàn)槿魶](méi)有a,b和c,則有NC≤|N(u)∪N(υ)|≤|V(G)|-|狖u,υ,x狚|<n-δ矛盾.說(shuō)明必有a或b或c,從而有C4.(2)δ≥3,此時(shí),分情況討論如下:情況1G中有一點(diǎn)x,滿足d(x)>δ.類(lèi)似δ±2時(shí)相應(yīng)討論知N(x)中有兩點(diǎn)相鄰,從而有C3.情況2G中任一點(diǎn)x均有d(x)=δ.情況2.1G中有一點(diǎn)x滿足N(x)中有兩點(diǎn)相鄰.此時(shí)有C3.情況2.2G中任一點(diǎn)u,N(u)中沒(méi)有相鄰兩點(diǎn).此時(shí)記x∈V(G),記x1∈N(x),則有|N(x)∪N(x1)|<|V(G)|;不然,若|N(x)∪N(x1)|=|V(G)|,則在這些情況下,將得出G=Kn2,n2和假設(shè)矛盾.記u∈V(G-N(x)-N(x1)),因u已和N(x)中點(diǎn)x1不相鄰,所以u(píng)必和N(x)狖x1狚中任一點(diǎn)均相鄰.否則,若N(x)狖x1狚中有點(diǎn)x2和u不相鄰,則有NC≤N(x1)∪N(x2)≤V(G)-N(x)-狖u狚≤n-δ-1,矛盾.以上說(shuō)明u和N(x)狖x1狚中任一點(diǎn)均相鄰.又u和N(x1)中點(diǎn)x不相鄰,同理知u必和N(x1)狖x狚中任一點(diǎn)均相鄰.此時(shí)(N(x)狖x1狚)∪(N(x1)狖x1狚)中有相鄰的兩點(diǎn),否則記y1,y2∈(N(x)狖x1狚)∪(N(x1)|狖x狚),則有記x2,x3為(N(x)狖x1狚)∪(N(x1)狖x狚)中相鄰的兩點(diǎn),則ux2x3u是C3,矛盾.至此,證明了δ≥3時(shí),G有C3.記C3為x1x2x3x1,則N(x1)V(C3),N(x2)V(C3),N(x3)V(C3)這三個(gè)點(diǎn)集中有:a有兩個(gè)點(diǎn)集,它們有公共點(diǎn),或b,有兩個(gè)點(diǎn)集中各有一點(diǎn),它們相鄰,否則,若沒(méi)有結(jié)論a和b,記x11∈N(x1)V(C3),x21∈N(x2)V(C3),則有NC≤|N(x11)∪N(x21)|≤|V(G)|-|N(x3)V(C3)|-|狖x3,x11,x21狚|n-δ-1,矛盾說(shuō)明有結(jié)論a和b,從而有C4.引理2Cm是2連通n階圖G的長(zhǎng)為m的圈,NC≥n-δ,u是G-Cm的一點(diǎn),|NCm(u)|≥2,x∈N+Cm(u)(或N-Cm(Gu)),x和N(u)V(Cm)中點(diǎn)均不相鄰,則G有長(zhǎng)為m+1的圈Cm+1.證明在引理2條件下,有下列結(jié)論之一:2)xi,xj∈NCm(u),使xi+1,xj+1∈E(G)或xi-1,xj-1∈E(G).因?yàn)槿魶](méi)有a和b,記xi,xj∈NCm(u)及由引理?xiàng)l件知,x∈N[u].當(dāng)xV(Cm)時(shí),x和xi+1,xj+1(或xi-1,xj-1)均不相鄰.當(dāng)x=xk∈N(Cm)時(shí),xk+1和xi+1,xj+1(或xk-1和xi-1,xj-1)均不相鄰,從而有NC≤|N(xi+1)∪N(xj+1)|≤|N(G)|-|N[u]|<n-δ,矛盾.從而說(shuō)明必有a或b.當(dāng)a成立時(shí),構(gòu)成的Cm+1為:x1x2xiuxi+1xi+2x1.當(dāng)b成立時(shí),構(gòu)成的Cm+1為:x1x2xiuxjxj+1xi+1xj+1xj+2x1(此時(shí)i<j和xi+1xj+1∈E(G)時(shí)構(gòu)成的Cm+1,其它情況類(lèi)似).下面證明本文定理2:定理22連通n(n≥6)階圖G,NG≥n-δ,則G是泛圈圖或證明假設(shè),證明G必是泛圈圖.在此假設(shè)下,由引理1知G有C3,C4.下面只要說(shuō)明在知道G有Cs,Cs+1的情況下,G也有Cs+2,這就證明了本定理.假設(shè)已知Cs,Cs+1是G的兩個(gè)圈,若u∈V(G-Gs)和xk∈N±Cs(u),滿足xk和N(u)V(Cs)中某點(diǎn)相鄰,此時(shí)則有Cs+2.如若對(duì)滿足|NCs(u)|≥1的G-Gs中任一點(diǎn)u,N±Cs(u)中任一點(diǎn)和N(u)(Cs)中點(diǎn)均不相鄰.此時(shí)分情況討論如下:情況1G-Cs中存在不同兩點(diǎn)x,y,滿足情況1.1NCs(x)=NCs(y)=狖xi,xj狚此時(shí)有xy∈E(G).這是因?yàn)槿魓yE(G),則記xk∈N(Cs)狖xi,xj狚且滿足xk∈狖xi+1,xj+1狚,則NC≤|N(x)∪N(y)|≤|V(G)|-|N[xk]狖xi,xj狚|-|狖x,y狚|<n-δ,矛盾.說(shuō)明xy∈E(G),類(lèi)似引理2的討論知xi+1xj+1∈E(G),從而有Cs+2.1)當(dāng)NCs(x)=狖xi,xi+1狚,NCs(y)=狖xj,xj+1狚時(shí),則G有Cs+2.2)當(dāng)Cs上有不連接的兩點(diǎn)xi,xj滿足xi,xj∈NCs(x)或xi,xj∈NCs(y)時(shí)(不妨認(rèn)為xi,xj∈NCs(y)),由引理2知Cs和x構(gòu)成Cs+1,注意到Cs+1的結(jié)構(gòu),所以有(可認(rèn)為前者成立).這就是說(shuō)N±Cs+1(y)|中有兩點(diǎn),它們和N(y)V(Cs+1)中點(diǎn)均不相鄰,從而由引理2知,有由Cs+1和y組成的Cs+2.情況2G-Cs中至多有一點(diǎn)x滿足|NCs(x)|≥2.此情況下,G必有Cs+2.因?yàn)槿魶](méi)有Cs+2,則V(Cs)有s-1階完全子圖.這是因?yàn)镚是2連通的,所以G-Cs中有一點(diǎn)y滿足|NCs(y)|=1,記NCs(y)=狖xi狚.則xi+1和xi-1相鄰,因若xi+1xi-1E(G),則NC≤|N(xi+1)∪N(xi-1)|≤|V(G)|-|N[y]狖xi狚|-|狖xi+1,xi-1狚|<n-δ,矛盾現(xiàn)假設(shè)xk(k為狖i+1,i+2,,i-2狚一值)和xi-1相鄰.在此假設(shè)下,xk+1也和xi-1相鄰,因?yàn)槿魓k+1xi-1E(G),注意到?jīng)]有Cs+2,所以有NC≤|N(xk+1)∪N(xi-1)|≤V(G)|-|N[y]狖xi狚|-|狖xk+1,xi-1狚|<n-δ,矛盾.從而xk+1xi-1E(G)不正確.由歸納法知xi-1和Cs狖xi-1狚中點(diǎn)均相鄰.xk,xt∈V(Cs)狖xi狚,均有xkxt∈E(G),因?yàn)槿魓kxtE(G),則NC≤|N(xk)∪N(xt)|≤|V(G)|-|N[y]狖xi狚|-|狖xk,xt狚|<n-δ,矛盾至此證明了N(Cs)狖xi狚是完全子圖.設(shè)路P:y1y2yk是G-Cs中滿足y1,yk和Cs中兩點(diǎn)xi,xj分別相鄰且k是最小的.顯然有|NCs(y)|=1或|NCs(yk)|=1,不妨NCs(y1)=狖xt狚.當(dāng)k≤3時(shí),注意到V(Cs)有s-1階完全子圖,所以有Cs+2和前面假設(shè)沒(méi)有Cs+2矛盾.當(dāng)k≥4時(shí),記xk∈V(Cs)狖xixj狚u∈N[xk]狖xty4狚,注意到?jīng)]有Cs+2.NC≤|N(y1)∪N(y