謝佳漫,王 艷

(閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，福建 漳州 363000)

獨立集理論是圖論重要的研究領(lǐng)域之一，其中最大獨立集問題是圖論的熱點研究問題.1990年，張存銓提出一類臨界獨立集問題[1].記獨立集的個數(shù)減去其鄰集的個數(shù)的值為獨立集的差，臨界獨立集是指某個獨立集滿足其差在所有獨立集的差中取得最大值.近幾年來，研究表明最大獨立集問題與臨界獨立集問題之間存在著密切的聯(lián)系.為此，針對這兩類獨立集，我們研究一類單圈圖的相關(guān)性質(zhì).

1 預(yù)備知識

本文所考慮的圖均為有限簡單圖G=(V(G)，E(G))，其中集合V(G)為G的頂點集，集合E(G)為G的邊集.對于v∈V(G)，稱N(v)={w∈V(G)：vw∈E(G)}為v∈V(G)的鄰集；對于X?V(G)，稱N(X)={v：v∈V(G)且N(v)∩X≠?}為X的鄰集；稱N[X]=X∪N(X)為X的閉鄰域；稱d(X)=|X|-|N(X)|為X的差，特別地，d(?)=0；稱d(G)=max{d(X)：X?V(G)}為G的臨界差；若X滿足d(X)=d(G)，則稱X為臨界集.令ker(G)為G的所有臨界集的交.Levit等人在2012年證明了G的所有臨界獨立集的交等于ker(G)[2].

若X中任意兩個頂點都不相鄰，則稱X為獨立集；記獨立集族ind(G)={X：X為G的獨立集}；設(shè)X∈ind(G)，?X′∈ind(G)，|X′|≤|X|，則稱X為最大獨立集，記最大獨立集的頂點數(shù)為α(G)；令core(G)為G的所有最大獨立集的交.

在圖G中ker(G)?core(G)[2]；當(dāng)圖G為二部圖時，則ker(G)=core(G)[3].

對于M?E(G)，若M中任意兩條邊都不相鄰，則稱M為G的匹配.記m∈M為匹配邊；若匹配M中某條邊與v關(guān)聯(lián)，則稱M飽和v；記|M(G)|為G的匹配邊數(shù)；若|M(G)|在G中取得最大值，則稱為最大匹配M，記最大匹配數(shù)為μ(G)；若匹配M能匹配G的所有頂點，則稱M為完美匹配；稱MΔM′=M∪M′-M∩M′為匹配M和M′的對稱差.

對于X?V(G)，G[X]為由X?V(G)所導(dǎo)出G的子圖.對于M?E(G)，G[M]為由M?E(G)所導(dǎo)出G的子圖.設(shè)G的點邊交替序列W=v0e1v1e2…vl-1elvl，其中1≤i≤l，ei=(vi-1，vi)，稱W為G的一條路徑；稱整數(shù)l為W的長；若l>0，vi≠vj(0≤i0，v0=vl且vi≠vj(1≤i

在單圈圖G中，|V(G)|-1≤α(G)+μ(G)≤|V(G)|[6]；在非K?nig-Egerváry單圈圖中，ker(G)=core(G)[7]，但在K?nig-Egerváry單圈圖中，ker(G)=core(G)不一定成立.例如，在圖1中ker(G1)={x，y}但core(G1)={x，y，z}而ker(G2)=core(G2)={a，b，c}.

圖1 K?nig-Egerváry單圈圖

若單圈圖G有完美匹配，則α(G)=μ(G)=|V(G)|/2，故α(G)+μ(G)=|V(G)|，所以圖G為K?nig-Egerváry圖.

如果能刻畫滿足ker(G)=core(G)的非二部的單圈K?nig-Egerváry圖，我們將更進(jìn)一步了解單圈圖的性質(zhì).為此，我們探討非二部的單圈K?nig-Egerváry圖的特殊情況，即具有完美匹配的非二部的單圈圖，研究其ker(G)和core(G)的性質(zhì).

2 主要結(jié)果

本節(jié)先介紹具有完美匹配的非二部的單圈圖G的基本性質(zhì)及其ker(G)，再分兩步論證其core(G).

性質(zhì)1 若圖G為非二部的單圈圖且包含完美匹配，則下列結(jié)論成立:

(1)圈為奇圈；

(2)完美匹配是唯一的.

證明：

(1)顯然成立，若圈為偶圈，則圖G為二部圖.(2)如果不唯一，則圖G至少存在兩個完美匹配，分別為M、M′，則MΔM′必為偶圈，而與單圈非二部圖矛盾.故命題成立.

□

性質(zhì)2 若圖G為非二部的單圈圖且包含完美匹配，則ker(G)=?.

證明：

由于圖G有完美匹配，故對于任意X?V(G)，|N(X)|≥|X|恒成立，即d(X)≤0.故臨界差d(G)=0.而空集的差為0，故空集為臨界集，因此空集與任一臨界集的交為空集，故ker(G)=?.

在單圈圖G上，對G的完美匹配M進(jìn)行劃分，分別為M1=M∩E(C)，M2=M∩E(N[C])-M1，M3=M-M1-M2.

首先考慮M3=?的情形.由性質(zhì)1可知，圖G有唯一的完美匹配和奇圈，則匹配在圈C上的邊數(shù)是唯一確定的且α(G)=|V(G)|/2.接下來對匹配在圈C上的邊數(shù)進(jìn)行分類討論core(G).為了方便討論，先將圖G劃分為A，B兩部分：設(shè)B為最大獨立集，即|B|=|V(G)|/2，A中只有兩個點相鄰，使得從A到B有完美匹配.顯然A中相鄰的兩個點在圈C上.另外，圈C上的點在A的點數(shù)比在B的點數(shù)多1.

定理3 若圖G為1個奇圈加1條懸掛邊，記懸掛點為b，則core(G)=.

證明：

顯然|M2|=1且b被M2飽和.記被M2飽和的另一個頂點為a.此時，點a、b分別屬于A和B.令a為A中相鄰的兩個點之一，如圖2所示.

圖2 圖G為1個奇圈加1條懸掛邊

此時∩(A{a})=?，又因為A{a}中的點互不相鄰，且|A{a}|=|B|-1，故∪(A{a})為G的最大獨立集，記為B′.而當(dāng)G-b為圈C，其最大獨立集的頂點數(shù)為|B|-1，故G-b中不存在G的最大獨立集.又因為B=(M1∩B)∪，因此core(G)=B∩B′=，故結(jié)論成立.

□

定理4 若圖G為1個奇圈加若干奇數(shù)(大于1)條懸掛邊，則core(G)=?.

證明：

記在圈C中被M2所飽和的點的個數(shù)記為t，其中3≤t≤|V(C)|且t為奇數(shù).設(shè)M2={m1，m2，…，mi，…，mt}，其中1≤i≤t.令mi=aibi，其中ai∈V(C)，bi?V(C)，如圖3所示.

圖3 圖G為1個奇圈加若干奇數(shù)(大于1)條懸掛邊

□

我們接下來考慮M3≠?的情形.在圖G中，設(shè)?(X)={uv∈E(G)：u∈X，v∈VX}為X的邊割.

在非二部的單圈圖G且包含完美匹配中，記頂點集合X=V(C)∪{v：被M2飽和的頂點}，頂點集合Y=V(G)X.此時G[Y]為森林，每一棵樹Tj有完美匹配，其中1≤j≤c(G[Y])，這里c(G[Y])表示G[Y]的連通分支數(shù)；邊割?(X)=?(Y)=c(G[Y])且對于e=xjyj∈?(X)，其中xj∈V(X)，yj∈V(Y)，e不是G的完美匹配邊.設(shè)樹Tj的根為yj.

因為樹Tj是二部圖且有完美匹配，因此存在兩個不同的最大獨立集Aj和Bj，使得樹的完美匹配邊的端點分別來自Aj、Bj.故Aj∩Bj=?，Aj∪Bj=V(Tj)，且|Aj|=|Bj|=|V(Tj)|/2.

結(jié)合情形M3=?的圖，對G[X]劃分為A，B兩部分：設(shè)B為最大獨立集，|B|=|V(G[X])|/2，A中只有兩個點相鄰，使得從A到B有完美匹配.顯然A中相鄰的兩個點在圈C上.另外，圈C上的點在A的點數(shù)比在B的點數(shù)多1.若xj∈A，則令yj所在的集合為Bj；否則令yj所在的集合為Aj，此時{xj}∪Bj為獨立集.接下來對匹配在圈C上的邊數(shù)進(jìn)行分類討論core(G).

證明：

在G[X]中取兩個最大獨立集為B和B′，且B∩B′=，其中b為圈C外被M2飽和的頂點且b∈B，其取法和記法與定理3的證明中相同.按下述取法取兩個G的最大獨立集分別為S、S′.

此時，

而在G-b中，其最大獨立集的個數(shù)為

而G的最大獨立集的個數(shù)為|V(G)|/2，故在G-b中，不存在G的最大獨立集.故b∈core(G).

另一方面，由于b∈core(G)，則N(N(b)∩Y)?core(G)，顯然

又因為Tj為一棵樹中，則包含N(N(b)∩Y)的最大獨立集Bj是唯一的，故

□

定理6 若單圈圖G(設(shè)G包含的圈為C)為非二部圖且包含完美匹配M，滿足|E(C)∩M|<(|E(C)|-1)/2，則core(G)=?.

證明：

此時，

□

利用反證法，由定理5和定理6可知，

推論8 若單圈圖G(設(shè)G包含的圈為C)為非二部圖且包含完美匹配M，則core(G)=?當(dāng)且僅當(dāng)|E(C)∩M|<(|E(C)|-1)/2.

由性質(zhì)2可得，

推論9 若單圈圖G(設(shè)G包含的圈為C)為非二部圖且包含完美匹配M，則ker(G)=core(G)=?當(dāng)且僅當(dāng)|E(C)∩M|<(|E(C)|-1)/2.

3 結(jié)束語

在本文中，通過研究包含完美匹配的單圈圖的最大獨立集的交、臨界集的交以及它們之間的關(guān)系，得到了兩類獨立集的交相等的等價條件.在后續(xù)的研究中，我們可以利用這個結(jié)論，進(jìn)一步研究相關(guān)單圈圖的刻畫，并探討單圈圖的最大獨立集的交與臨界集的交之間的關(guān)系.