楊田羽，王 勤

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

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

1 準(zhǔn)備工作

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

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

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

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

引理1.2[4]若G是一個(gè)有偶數(shù)個(gè)頂點(diǎn)的連通無爪圖，則圖G有完美匹配。

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

2 主要結(jié)果及其證明

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

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

(1)

則圖G是幾乎導(dǎo)出匹配可擴(kuò)的。

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

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

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

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

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

(2)

對滿足1≤k

情形1M飽和頂點(diǎn)x

若M飽和頂點(diǎn)x，易知|M|=1。由于圖G′是2-可擴(kuò)的，則任一邊數(shù)為1的導(dǎo)出匹配M可以擴(kuò)充為G′的一個(gè)完美匹配(圖1)。

圖1 M飽和頂點(diǎn)xFigure 1 The vertex x is M-saturated

情形2M不飽和頂點(diǎn)x

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

情形2.1H是連通的

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

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

情形2.2H是不連通的

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

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

因?yàn)閳DG是無爪圖，由引理1.3可知：

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

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

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

=|V(H1)|+5，

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

=|V(H2)|+5。

從而，頂點(diǎn)u和頂點(diǎn)v的度和滿足

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

(3)

又因?yàn)?/p>

(4)

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

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

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

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

計(jì)算可得|V(M)|≤5，即|M|≤2。因?yàn)閳DG′是2-可擴(kuò)的，所以匹配M可以擴(kuò)充為圖G′的一個(gè)完美匹配。

綜上，圖G′是導(dǎo)出匹配可擴(kuò)的，從而圖G是幾乎導(dǎo)出匹配可擴(kuò)的，定理2.1得證。

推論2.2設(shè)圖G是一個(gè)有2n-1個(gè)頂點(diǎn)的無爪圖，若圖G的頂點(diǎn)的最小度滿足

δ(G)≥n+1，

(5)

則圖G是幾乎導(dǎo)出匹配可擴(kuò)的。

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

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

則圖G中頂點(diǎn)u和頂點(diǎn)v的度和滿足

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

由定理2.1可知，圖G是幾乎導(dǎo)出匹配可擴(kuò)的。

定理2.3不存在幾乎導(dǎo)出匹配可擴(kuò)的二部圖。

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

圖4 二部圖G與頂點(diǎn)x的聯(lián)圖G′Figure 4 The graph G′ obtained by joining vertex x to each vertex of G

因?yàn)閨A|<|B|，所以|A|-1<|B|。易知，圖H沒有完美匹配。所以圖G′不是導(dǎo)出匹配可擴(kuò)的，因此不存在幾乎導(dǎo)出匹配可擴(kuò)的二部圖G。

3 結(jié) 語

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