幾乎導出匹配可擴圖的一些度條件

楊田羽，王 勤

(1.中國計量大學 經濟與管理學院，浙江 杭州 310018；2.中國計量大學 理學院，浙江 杭州 310018)

匹配問題在圖論的相關研究中一直是一個熱門問題，它不僅包含著一系列豐富的理論問題，還在實際應用中得到進一步的發(fā)展[1-2]。1980年，PLUMMER[3]提出了n-可擴圖的概念，學者們圍繞n-可擴圖進行了大量的研究，并取得了一系列研究成果[4-6]。1998年，原晉江[7]提出了導出匹配可擴圖的概念。自此，關于圖的導出匹配可擴性和導出匹配可擴圖的度條件的研究成果層出不窮，例如導出匹配可擴二部圖的度條件[8]，導出匹配可擴圖和導出匹配可擴二部圖的度和條件[9,10]，結合圖的導出匹配可擴性[11]以及極大導出匹配可擴圖和極大非導出匹配可擴圖的刻畫，等等。楊帆等[12]研究了頂點數為2n的連通無爪圖的導出匹配可擴性及其最小度條件為2┌-n/2┐+1。王勤等[13]研究了導出匹配可擴無爪圖的度和條件。在此基礎上，本文利用無爪圖導出匹配的性質和幾乎導出匹配可擴圖的定義，進一步討論幾乎導出匹配可擴無爪圖的一些度條件，并探討二部圖的幾乎導出匹配可擴性。

1 準備工作

本文研究的圖均為簡單無向有限圖。對于圖G，我們分別用V(G)和E(G)來表示圖G的頂點集和邊集。對任一頂點u∈V(G)，用

NG(u)={v∈V(G){u}|uv∈E(G)}

表示頂點u在圖G中的鄰集。將圖G中連接頂點u的邊的數目稱為頂點u的度，記為dG(u)，其中

δ(G)=min{dG(u)|u∈V(G)}

引理1.2[4]若G是一個有偶數個頂點的連通無爪圖，則圖G有完美匹配。

引理1.3[12]若M是無爪圖G的一個導出匹配，則對任一頂點u∈V[G-V(M)]，有|N(u)∩V(M)|≤4。

2 主要結果及其證明

定理2.1設圖G是一個有2n-1個頂點的無爪圖，若對圖G中任意不相鄰的頂點u和v，有

d(u)+d(v)≥2n+1，

(1)

則圖G是幾乎導出匹配可擴的。

證明取任意頂點x?V(G)，將x與G中的每個頂點連接，得到x與G的聯圖，記為G′=G∨{x}。欲證圖G是幾乎導出匹配可擴的，只需證明圖G′是導出匹配可擴的。

已知圖G中任意不相鄰的頂點u和v滿足度和條件(1)，有

d(u)+d(v)≥2n+1。

而圖G′=G∨{x}中，子圖G的所有頂點均與x相連，則對圖G′中任意不相鄰的頂點u和v，有

d(u)+d(v)≥2n+3。

(2)

對滿足1≤k

情形1M飽和頂點x

若M飽和頂點x，易知|M|=1。由于圖G′是2-可擴的，則任一邊數為1的導出匹配M可以擴充為G′的一個完美匹配(圖1)。

圖1 M飽和頂點xFigure 1 The vertex x is M-saturated

情形2M不飽和頂點x

若M不飽和頂點x，則假定存在一點y∈V[G-V(M)]，將連接點x和點y的邊看作一個匹配M′，且|V(M′)|=2，記H=G′-V(M)-V(M′)。

情形2.1H是連通的

此時，圖H是一個有2n-|V(M)|-2個頂點的無爪圖。由引理1.2可知，圖H有完美匹配M″，從而M包含于G′的完美匹配M∪M′∪M″中(圖2)。

圖2 M不飽和頂點x且H是連通的Figure 2 The vertex x is M-unsaturated and H is connected

情形2.2H是不連通的

令H1和H2是H的兩個分支，假設u∈V(H1)，v∈V(H2)(圖3)。

圖3 M不飽和頂點x且H是不連通的Figure 3 The vertex x is M-unsaturated and H is disconnected

因為圖G是無爪圖，由引理1.3可知：

|NG(u)∩V(M)|≤4，
|NG(v)∩V(M)|≤4。

即匹配M中分別有至多4個頂點與u，v相鄰。則頂點u和頂點v在圖G′中的度滿足：

dG′(u)≤|V(H1)|-1+4+|V(M′)|

=|V(H1)|+5，

dG′(v)≤|V(H2)|-1+4+|V(M′)|

=|V(H2)|+5。

從而，頂點u和頂點v的度和滿足

dG′(u)+dG′(v)≤|V(H1)|+|V(H2)|+10。

(3)

又因為

(4)

則根據式(2)，(3)，(4)，有

2n+3≤dG′(u)+dG′(v)

≤|V(G′)|-|V(M)|-|V(M′)|+10

=2n+8-|V(M)|。

計算可得|V(M)|≤5，即|M|≤2。因為圖G′是2-可擴的，所以匹配M可以擴充為圖G′的一個完美匹配。

綜上，圖G′是導出匹配可擴的，從而圖G是幾乎導出匹配可擴的，定理2.1得證。

推論2.2設圖G是一個有2n-1個頂點的無爪圖，若圖G的頂點的最小度滿足

δ(G)≥n+1，

(5)

則圖G是幾乎導出匹配可擴的。

證明已知圖G中的頂點滿足最小度條件(5)，那么對于圖G中任意不相鄰的頂點u和v，有

d(u)≥n+1，d(v)≥n+1。

則圖G中頂點u和頂點v的度和滿足

d(u)+d(v)≥(n+1)+(n+1)=2n+2>2n+1。

由定理2.1可知，圖G是幾乎導出匹配可擴的。

定理2.3不存在幾乎導出匹配可擴的二部圖。

證明假設圖G是一個有二部劃分(A，B)的二部圖，|A|+|B|=2n-1，且|A|<|B|。取任意頂點x?V(G)，將x與圖G中的每個頂點連接，得到x與圖G的聯圖，記為G′=G∨{x}?，F將頂點x與任一頂點y∈A相連的邊xy看作圖G′的一個導出匹配M。記圖H=G′-V(M)見圖4)。

圖4 二部圖G與頂點x的聯圖G′Figure 4 The graph G′ obtained by joining vertex x to each vertex of G

因為|A|<|B|，所以|A|-1<|B|。易知，圖H沒有完美匹配。所以圖G′不是導出匹配可擴的，因此不存在幾乎導出匹配可擴的二部圖G。

3 結 語

在本文中，我們通過研究圖的完美匹配與幾乎導出匹配可擴性的關系，得到了幾乎導出匹配可擴無爪圖的度和條件和最小度條件，并證明了不存在幾乎導出匹配可擴的二部圖。若圖G是一個頂點數為2n-1的無爪圖，我們證明了如果對圖G中任意不相鄰的頂點u和v，有d(u)+d(v)≥2n+1，那么圖G是幾乎導出匹配可擴的；并證明了如果圖G的最小度δ(G)≥n+1，那么圖G是幾乎導出匹配可擴的。在后續(xù)的研究中，我們可以利用幾乎導出匹配可擴圖的性質，進一步研究相關極圖的刻畫，并探討圖的幾乎導出匹配可擴性與圖的連通性之間的關系。