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

張小霞，余 鯤，黃明芳

(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é)論。