• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    獨立點數(shù)為3的圖的Z3-連通性

    2022-01-27 09:52:32張小霞黃明芳
    關(guān)鍵詞:斷言子圖連通性

    張小霞,余 鯤,黃明芳

    (1.信陽師范學院 數(shù)學與統(tǒng)計學院,河南 信陽 464000;2.武漢理工大學 理學院,湖北 武漢 430070)

    0 引言

    本文所考慮的圖都是有限的簡單無環(huán)圖.沒有定義的術(shù)語及符號參見BONDY和MURTY的論著[1]。

    設(shè)G是一個圖,S是G的一個點集,若S中任意兩點在G中都不相鄰,則稱S是獨立集。G的最大獨立集所包含點的個數(shù)被稱為G的獨立點數(shù),用α(G)表示。對于兩個子集A,B?V(G),用e(A,B)來表示一個端點在A中、另一個端點在B中的所有邊的個數(shù)。若A={v},為了簡單起見,用e(v,B)表示e({v},B)。圖G的鄰集用NG(x)表示,可簡寫為N(x)。

    對每個點v∈V(G)都成立,則稱圖G是Zk-連通的。很顯然,若圖G是Z3-連通的,則存在處處非零3-流。

    群連通的概念是“處處非零流”的推廣,最早是由JAEGER等[2]引入的,并且提出了與3-流猜想相對應(yīng)的Z3-連通猜想。

    猜想(JAEGER等[2]) 每個5-邊連通圖都是Z3-連通的。

    Z3-連通猜想的提出為3-流猜想的研究提供了另一思路。許多專家學者都對此做了大量研究,尤其是利用度條件來保證Z3-連通的存在性[3-5]。但直到2012年THOMASSEN[6]才對此猜想的研究取得突破性的進展,證明了每一個8-邊連通圖都是Z3-連通的。此結(jié)果很快被LOVASZ等[7]進一步改進,證明了每一個6-邊連通圖都是Z3-連通的。但目前,此猜想還沒有解決。2016年YANG等[8]刻畫了獨立點數(shù)為2的圖的Z3-連通性。受此啟發(fā),本文研究了獨立點數(shù)為3的5-邊連通圖的Z3-連通性,證明了Jaeger的Z3-連通猜想對于獨立點數(shù)為3且點連通度不大于5的圖是成立的。

    1 預備知識

    引理1[2,9-11]設(shè)Z3為3階循環(huán)群,則

    (2)C2是Z3-連通的。

    (3)W2k是Z3-連通的,其中k為正整數(shù)。

    設(shè)H是圖G的一個子圖,若把H中的所有點都粘在一起,并把此過程所產(chǎn)生的所有環(huán)都刪掉,則稱G收縮H,記為G/H。

    引理2[9,10]設(shè)H為G的一個Z3-連通子圖。若G/H是Z3-連通的,則G也是Z3-連通的。

    由文獻[8]中定理1.3,容易得出如下結(jié)論:

    引理3 設(shè)G是一個δ(G)≥4的2-邊連通簡單圖。若α(G)≤2,則G是Z3-連通的。

    設(shè)NG(v)={v1,v2,…,vm}(m≥4)。如果將vv1和vv2兩條邊去掉,添加一條新邊v1v2所得到的圖記為G[vv1,vv2],則有下面結(jié)論成立。

    引理4[11]如果G[vv1,vv2]是Z3-連通的,那么圖G也是Z3-連通的。

    引理5 設(shè)G是5-邊連通圖并且α(G)=3。若G包含極大Z3-連通子圖H且α(G-H)≤2,那么圖G是Z3-連通的。

    證明設(shè)G*=G/H,v*為收縮H所形成的新點,則α(G*-v*)=α(G-H)≤2。設(shè)e為G*-v*的一條割邊,G1和G2是G*-v*-e的兩個連通分支,則α(G1)=α(G2)=1。因為G是5-邊連通圖,所以G*中v*的度dG*(v*)≥5并且G*-v*的最小度δ(G*-v*)≥4。于是G1和G2都是階數(shù)大于等于5的完全圖并且e(v*,G1)≥2或者e(v*,G2)≥2。由引理1和引理2可知,G1+H或者G2+H是Z3-連通的,這與H是極大Z3-連通子圖矛盾!因此G*-v*是2-邊連通的。由引理3知,G*-v*是Z3-連通的。再根據(jù)引理2,從而G也是Z3-連通的。證畢。

    2 主要結(jié)論

    定理1 設(shè)G是5-邊連通圖。如果α(G)=3并且點連通度κ(G)≤4,那么圖G是Z3-連通的。

    證明設(shè)S為圖G的最小點割,G1和G2為G-S的兩個分支,則α(G1)+α(G2)≤3。因此α(G1)=1或α(G2)=1。

    不失一般性,假設(shè)α(G1)=1即G1=Km(m≥1)并且假設(shè)圖G不是Z3-連通的。

    斷言1 不存在點v∈S使得G1+v是Z3-連通的。

    斷言1的證明 假設(shè)存在點v∈S使得G1+v是Z3-連通的,則由引理1可知|V(G1)|≥4。設(shè)H是圖G中包含G1+v的極大Z3-連通子圖。若H∩G2≠?,則顯然有α(G-H)≤α(G2)=2。若H∩G2=?,則α(G-H)≤2。否則假設(shè)α(G-H)=3,注意到對任意點x∈V(G-H),都有e(x,H)≤1,所以必存在u∈V(H)使得α(G)=4,矛盾!由引理5可知,G是Z3-連通的,矛盾!故斷言1成立。

    斷言2 2≤m≤4且κ(G)=4。

    斷言2的證明 因為G是5-邊連通圖并且κ(G)≤4,所以可得m≠1并且存在點v∈S使得e(v,G1)≥2。如果m≥5,由引理1和2可知,G1+v是Z3-連通的,與斷言1矛盾!故2≤m≤4。這也意味著κ(G)≠1。

    當m=4時,對任意v∈S,由斷言1可知e(v,G1)≤2。又因為|S|=4并且e(G1,S)≥8,所以e(v,G1)=2。設(shè)N(v)∩G1={v1,v2}。下面考慮圖G[vv1,vv2]。設(shè)H=G1+S-v+v1v2。很明顯,它是Z3-連通的。再設(shè)G*=G[vv1,vv2]/H且v*是收縮H而形成的新點。易知S中無相鄰邊,因此d(v*)≥7并且G*-v是4-邊連通的。如果存在兩個點u,w∈V(G2)使得{u,w,v*}是一個獨立集,那么必然存x,y∈V(H)使得{u,w,x,y}是圖G的獨立集,這與α(G)=3矛盾!因此α(G*-v)≤2。由引理3可知,G*-v是Z3-連通的。由引理1和2可知,G[vv1,vv2]是Z3-連通的。再根據(jù)引理5,G也是Z3-連通的,矛盾!

    當m=3時,由斷言1可知,最多有一個點v∈S使得e(v,G1)≥3。而由于e(G1,S)≥9,所以e(v,G1)≥2,v∈S。因為α(G)=3,所以G[S]一定包含一條邊,不妨設(shè)為xy。若e(x,G1)=3或e(y,G1)=3,則G1+{x,y}包含Z3-連通子圖W4作為生成子圖,與斷言1矛盾!故e(x,G1)=2和e(y,G1)=2,并且

    |N(x)∩N(y)∩V(G1)|=1。

    而此時,G1+{x,y}也包含W4作為一個生成子圖,因而是Z3-連通的,仍然與斷言1矛盾!

    當m=2時,設(shè)V(G1)={v1,v2},則

    |N(v1)∩N(v2)|=S。

    任意選取v∈S,考慮圖G[vv1,vv2]。與m=4時類似,也可證明G是Z3-連通的,與斷言1矛盾!證畢。

    3 結(jié)束語

    文獻[12]完美地刻畫了獨立點數(shù)為2的圖的Z3-連通性,同時猜想:獨立點數(shù)為3的5-邊連通圖是Z3-連通的。本文證明了此猜想在點連通度小于等于4時是成立的。對于點連通度等于5的情況還在進一步研究當中,旨在推廣LI等[13]所做的關(guān)于獨立點數(shù)為3的處處非零3-流的結(jié)論。

    猜你喜歡
    斷言子圖連通性
    von Neumann 代數(shù)上保持混合三重η-*-積的非線性映射
    偏序集及其相關(guān)拓撲的連通性?
    C3-和C4-臨界連通圖的結(jié)構(gòu)
    特征為2的素*-代數(shù)上強保持2-新積
    擬莫比烏斯映射與擬度量空間的連通性
    Top Republic of Korea's animal rights group slammed for destroying dogs
    臨界完全圖Ramsey數(shù)
    河道-灘區(qū)系統(tǒng)連通性評價研究
    基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
    高穩(wěn)定被動群集車聯(lián)網(wǎng)連通性研究
    通信學報(2016年11期)2016-08-16 03:20:04
    雷波县| 潍坊市| 正宁县| 秦皇岛市| 绥滨县| 阆中市| 耿马| 元朗区| 诸城市| 婺源县| 甘谷县| 临猗县| 湘乡市| 天长市| 家居| 平凉市| 连山| 安顺市| 吐鲁番市| 同江市| 怀安县| 新源县| 聂荣县| 会同县| 洪江市| 邮箱| 安乡县| 峡江县| 渝中区| 桃园市| 太保市| 洛阳市| 临武县| 攀枝花市| 长宁县| 双鸭山市| 朝阳区| 澄江县| 涞水县| 阳谷县| 长子县|