• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2022-08-08 06:12:16覃城阜莫芬梅
      關(guān)鍵詞:斷片斷言對(duì)稱性

      覃城阜,莫芬梅

      (南寧師范大學(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。

      猜你喜歡
      斷片斷言對(duì)稱性
      新語(yǔ)
      von Neumann 代數(shù)上保持混合三重η-*-積的非線性映射
      一類截?cái)郒ankel算子的復(fù)對(duì)稱性
      巧用對(duì)稱性解題
      最后的斷片
      橫向不調(diào)伴TMD患者髁突位置及對(duì)稱性
      特征為2的素*-代數(shù)上強(qiáng)保持2-新積
      Top Republic of Korea's animal rights group slammed for destroying dogs
      巧用對(duì)稱性解題
      路、圈的Mycielskian圖的反魔術(shù)標(biāo)號(hào)
      金溪县| 肃宁县| 青岛市| 双鸭山市| 凉山| 册亨县| 井研县| 阜南县| 南京市| 雅安市| 信阳市| 福海县| 汶川县| 天门市| 太仓市| 汉沽区| 喀什市| 靖宇县| 阿拉善右旗| 黔西县| 绥阳县| 五莲县| 连城县| 惠水县| 绍兴市| 定南县| 安多县| 兴城市| 清新县| 五大连池市| 洪江市| 新乡县| 海城市| 航空| 桦川县| 孝昌县| 潼关县| 昌吉市| 朝阳县| 鄂托克前旗| 汾阳市|