一類單圈圖的最大獨(dú)立集的交

謝佳漫,王 艷

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

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

1 預(yù)備知識

本文所考慮的圖均為有限簡單圖G=(V(G)，E(G))，其中集合V(G)為G的頂點(diǎn)集，集合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的所有臨界獨(dú)立集的交等于ker(G)[2].

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

在圖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的所有頂點(diǎn)，則稱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的點(diǎn)邊交替序列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為最大獨(dú)立集，即|B|=|V(G)|/2，A中只有兩個點(diǎn)相鄰，使得從A到B有完美匹配.顯然A中相鄰的兩個點(diǎn)在圈C上.另外，圈C上的點(diǎn)在A的點(diǎn)數(shù)比在B的點(diǎn)數(shù)多1.

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

證明：

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

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

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

□

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

證明：

記在圈C中被M2所飽和的點(diǎn)的個數(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且包含完美匹配中，記頂點(diǎn)集合X=V(C)∪{v：被M2飽和的頂點(diǎn)}，頂點(diǎn)集合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是二部圖且有完美匹配，因此存在兩個不同的最大獨(dú)立集Aj和Bj，使得樹的完美匹配邊的端點(diǎn)分別來自Aj、Bj.故Aj∩Bj=?，Aj∪Bj=V(Tj)，且|Aj|=|Bj|=|V(Tj)|/2.

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

證明：

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

此時，

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

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

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

又因為Tj為一棵樹中，則包含N(N(b)∩Y)的最大獨(dú)立集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é)束語

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