C3-和C4-臨界連通圖的結(jié)構(gòu)

覃城阜，莫芬梅

(南寧師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣西 南寧 530001)

1 主要結(jié)果

本文所討論的圖都是簡(jiǎn)單圖。設(shè)G=(V,E)是一個(gè)圖,其中V表示頂點(diǎn)集,E表示邊集。對(duì)于W?V,記NG(W)={y|y?W且y與W中的點(diǎn)相鄰}。特別地，當(dāng)W={t}時(shí)將NG({t})簡(jiǎn)記為NG(t)。與x關(guān)聯(lián)的邊的數(shù)目稱為x的度數(shù),記為dG(x),顯然dG(x)=|NG(x)|。令Vk(G)={x∈V(G)|d(x)=k}。在不引起混淆的情況下可以省略下標(biāo)G。

設(shè)G是連通圖，T是V(G)的一個(gè)子集,如果G-T至少有2個(gè)分支,稱T為G的點(diǎn)割。特別地,如果|T|=(G),則稱T為G的最小點(diǎn)割。如果|T|=l,則稱T是l-點(diǎn)割。設(shè)T為G的最小點(diǎn)割,x是T中的一個(gè)點(diǎn),A是G-T的一個(gè)分支,由最小點(diǎn)割的定義可知N(x)∩A≠?。

設(shè)G是連通圖，如果G的每個(gè)頂點(diǎn)都包含在最小點(diǎn)割中,則稱G是臨界圖；如果G的每條邊都包含在最小點(diǎn)割中,則稱G是一個(gè)收縮臨界圖。

定理1[1]如果G是C3-臨界圖,則κ(G)≥6；如果G是C-臨界圖,則κ(G)≥8。

設(shè)G為至少有k+2個(gè)頂點(diǎn)的k-連通圖。如果對(duì)G的每條邊e都有κ(G-e)<κ(G),則稱G是極小k-連通圖。因此，對(duì)極小k-連通圖G的任意一條邊e=xy,G-e有一個(gè)點(diǎn)割T分離x和y，且|T|=k-1。此外,G-xy-T恰好包含2個(gè)分支,且其中一個(gè)包含x,另一個(gè)包含y。若圖G既是Cm-臨界圖，又是極小k-連通圖,則稱G是Cm-臨界極小連通圖,這里k=κ(G)。

Ando等[11]證明了以下定理2。

定理2[11]設(shè)G是C2-臨界極小6-連通圖,則G的每一個(gè)頂點(diǎn)都與一個(gè)6度點(diǎn)相鄰。

顯然,C3-臨界極小6-連通圖一定是C2-臨界極小6-連通圖。由定理2,C3-臨界極小6-連通圖的每一個(gè)點(diǎn)都與一個(gè)6度點(diǎn)相鄰。設(shè)G6是圖G中由6度點(diǎn)導(dǎo)出的子圖,Poster[17]證明了如下定理3。

受文獻(xiàn)[6]中證明方法的啟發(fā)，本文對(duì)C3-臨界極小6-連通圖中的局部結(jié)構(gòu)進(jìn)行討論，證明這類圖中每個(gè)頂點(diǎn)都與2個(gè)6度點(diǎn)相鄰,由此可以推出Poster的結(jié)果。

定理4設(shè)x是C3-臨界極小6-連通圖的一個(gè)頂點(diǎn),則x與2個(gè)6度頂點(diǎn)相鄰。

由定理4 可知，G6中每個(gè)分支的最小度為2,于是每個(gè)分支至少有1個(gè)圈,因此定理3可以作為定理4的一個(gè)推論。

基于對(duì)C3-臨界極小6-連通圖結(jié)構(gòu)的認(rèn)識(shí)，本文對(duì)C4-臨界連通圖的連通性進(jìn)行討論,得到如下定理5。

定理5設(shè)G是C4-臨界連通圖,則κ(G)≥7。

由定理1及定理5可以提出如下問(wèn)題。

問(wèn)題1Cm-臨界連通圖的連通度至少為m+3。

2 預(yù)備引理

本章給出一些引理，這些引理在主要結(jié)果的證明中將會(huì)用到。

引理1[1]設(shè)G是一個(gè)連通圖,E0?E(G),M和M′是2個(gè)不同的E0-斷片,并且U=N(M),U′=N(M′)。如果(U′∩M)∪(U′∩U)∪(U∩M′)含E0中1個(gè)元素,則下面結(jié)論成立：

③ 如果M∩M′≠?，x∈(U′∩M)∪(U′∩U)∪(U∩M′)，且N(x)∩M∩M′=?，則

N(M∩M′)=(U′∩M)∪(U′∩U)∪(U∩M′)。

引理3[11]設(shè)M是k-連通圖G的一個(gè)斷片,S?N(M)。如果|N(S)∩M|<|S|,則M=N(S)∩M。

引理4設(shè)G是一個(gè)連通圖,a、b是G的2個(gè)頂點(diǎn),使得N(a)-=N(b)-{a},則a∈U當(dāng)且僅當(dāng)b∈U,這里U是G的一個(gè)最小點(diǎn)割。

類似引理4的證明，容易得到如下引理5。

引理5設(shè)G是C2-臨界k-連通圖,M={a,b}是G的一個(gè)斷片，M′是一個(gè)az-斷片,其中z∈N(M)。如果N(M)-{z}?N(b),則M?N(M′)。

引理6[18]設(shè)G是一個(gè)極小k-連通圖,則G-Vk(G)是一個(gè)森林。

設(shè)G是一個(gè)極小k-連通圖,C是G的一個(gè)圈，則由引理6可知V(C)∩Vk≠?。

3 定理4的證明

引理7設(shè)G是一個(gè)C3-臨界極小6-連通圖,H={x,y}是G的一個(gè)斷片,則以下結(jié)論成立：

①x和y中有1個(gè)6度點(diǎn)；

② 如果d(x)=7,則V(y)∩N(H)?V6(G)。

證明由H={x,y}可知d(x)≤7,d(y)≤7。假設(shè)x和y都是7度點(diǎn),則N(x)=N(H)∪{y}，N(y)=N(H)∪{x}。因?yàn)镚是一個(gè)極小6-連通圖,所以G-xy有一個(gè)5-點(diǎn)割S，將x和y分離。注意到N(H)?NG-xy(x)∩NG-xy(y),即N(H)?S,這與S是5-點(diǎn)割矛盾。因此①成立。

下面證明②成立。由d(x)=7,可知N(H)?N(x)。由①可得d(y)=6。設(shè)N(H)={x1,x2,…,x6},不失一般性,設(shè)N(y)∩N(H)={x1,…,x5}。

引理8設(shè)G是一個(gè)C3-臨界極小6-連通圖,H是G的一個(gè)關(guān)于邊ab的斷片,且滿足|H|≤2，則d(b)=6,或者N(a)∩V6(G)∩H≠?。

證明如果H?V6(G),則由N(a)∩H≠?可知N(a)∩V6(G)∩H≠?，于是引理成立。故不妨設(shè)u∈H滿足d(u)=7,則|H|=2。設(shè)H={u,v},由引理7可知d(v)=6。如果av∈E(G),則N(a)∩V6(G)∩H≠?,引理成立。若av?E(G),則vb∈E(G),由引理7可得,d(b)=6,引理成立。證畢。

證明不妨設(shè)H是滿足引理?xiàng)l件的極小斷片,如果|H|≤2,由引理8,N(a)∩V6(G)∩N(H)≠?或者N(a)∩V6(G)∩H≠?,引理成立。于是不妨設(shè)|H|≥3。設(shè)a1∈N(a)∩H,M是一個(gè)斷片滿足{a,a1}?N(M)。

本章剩余部分將證明定理4。設(shè)u∈V(G),由定理3可知u有一個(gè)6度鄰點(diǎn),記為u1。令E′(u)=E(u)-{uu1}。假設(shè)N(u)∩V6(G)={u1},由引理9,下面斷言1成立。

斷言3存在一個(gè)E′(u)-斷片H,使得u1∈N(H)。

由斷言3,選取一個(gè)E′(u)-斷片H,使得u1∈N(H)且|H|盡可能小。設(shè)u2∈N(u)∩N(H)-{u1}，若|H|≤2,則由引理8可得d(u2)=6或者N(u)∩V6(G)∩H≠?，此時(shí)有|N(u)∩V6(G)|≥2,矛盾。所以可設(shè)|H|≥3。設(shè)u3∈N(u)∩H。

斷言4存在一個(gè)斷片M,使得{u,u1,u3}?N(M)。

由斷言4，取斷片M使得{u,u1,u3}?N(M)，則{u,u1}?N(H)∩N(M)。

斷言5H?N(M)。

下面證明定理4。

4 定理5的證明

本章先給出3個(gè)輔助引理，再給出定理5的證明。

引理10設(shè)G是C4-臨界圖6-連通圖。若A={a，b}是一個(gè)連通斷片,x∈N(A),xa∈E(G)且xa不在三邊形中。令TB是包含{x,a}的最小點(diǎn)割，B是TB-斷片。若B∩N(A)={c，d},則A?TB且cd∈E(G)。

先證明A?TB。由xa不在三邊形中可知b與x不相鄰，故b與TA-{x}中的每一個(gè)點(diǎn)都相鄰，由引理5可知A?TB。

由斷言6及對(duì)稱性，不妨設(shè)B∩C=?。

由Cm-臨界連通圖的定義可知下面引理12成立。

引理12設(shè)G是Cm-臨界連通圖，e∈E(G)是G的邊，若κ(G-e)=κ(G)，則G-e也是Cm-臨界連通圖。

下面證明定理5。

定理5的證明設(shè)κ(G)≤6。由定理1可知κ(G)=6。由引理12,不妨設(shè)G是極小C4-臨界連通圖。由極小C4-臨界連通圖的定義可知G是極小6-連通圖。若G中不存在K5,則G是C-臨界連通圖,由定理1可知κ(G)≥8,矛盾。故G中存在K5,設(shè)G[{x,x1,x2,x3,x4}]?K5。注意到G是極小6-連通圖,由引理6可知G中每一個(gè)圈上都有 6 度點(diǎn)?？紤]三邊形xx1x2,由對(duì)稱性，不妨設(shè)x是6度點(diǎn)。令N(x)={x1,x2,x3,x4,x5,x6}。

斷言8x5x6?E(G)。

斷言9xtxi?E(G),這里t∈{5,6},i∈{1,2,3,4}。

證明由對(duì)稱性,只證明x5x1?E(G),其他類似可以證明。

設(shè)x5x1∈E(G),則x5x1x是三邊形。取完全圖Km使得{x5,x1,x}?Km。在滿足m≤4 的前提下,使m盡可能大。取TA是包含Km的最小點(diǎn)割,A是TA-斷片。

斷言9.1A∩B=?。

由斷言9.1及斷言9.2可知A?TB。

斷言 9.3|A|=2。

由斷言9.3,設(shè)A={x6,u}。由x5x6?E(G)可知x6x1∈E(G)。此時(shí)x5與x6的位置完全對(duì)稱，因此,由斷言9.3,不妨設(shè)B?TA,B={x5,v}。

斷言 9.4|TB∩TA|=2。

下面證明定理5。

斷言10A1∩A2=?。

由斷言10及斷言11可知A1?T2。注意到A1和A2是完全對(duì)稱的,因此可設(shè)A2?T1。

斷言12|A1|=|A2|=2。

由x5x6?E(G),TC-{x5}?N(x6)。由引理5可知A1?TC。