導(dǎo)出匹配可擴(kuò)圖的一些結(jié)果

張媛郭靜

(鄭州鐵路職業(yè)技術(shù)學(xué)院，河南 鄭州 450052)

本文所討論的圖G都是有限簡(jiǎn)單無向圖。V(G)、E(G)分別表示圖G的頂點(diǎn)集和邊集，o(G)表示圖G的奇分支數(shù).設(shè)S?V(G)，S的鄰集NG(S)={υ|υ∈V(G)S，且存在一點(diǎn) ν∈S，使得 υν∈E(G)};S 的導(dǎo)出邊集 E(S)={υν|υν∈E(G)，且 υ，ν∈S}.設(shè) M?E(G)，記 V(M)={υ|υ∈V(G)，且存在ν∈V(G)，使得 υν∈E(G)}.Kn表示有 n個(gè)頂點(diǎn)的完全圖.圖G和H的聯(lián)合，記為G∪H=(V(G)∪V(H)，E(G)∪E(H))，kG表示G的k個(gè)不相交拷貝的聯(lián)合。圖G和H的交記為G+H，它是由G∪H添加上G和H之間所有可能的邊得到.設(shè)M?E(G)，若M中任何兩邊都沒有共同的端點(diǎn)，則稱M是圖G的一個(gè)匹配;若V(M)=V(G)，則稱匹配M是圖G的一個(gè)完美匹配;若匹配M滿足E(V(M))=M，則稱M是圖G的一個(gè)導(dǎo)出匹配;若圖G的任何一個(gè)導(dǎo)出匹配M都包含在圖G的一個(gè)完美匹配中，則稱圖G是導(dǎo)出匹配可擴(kuò)圖.設(shè)S?V(G)，Ms是G［S］中的最大導(dǎo)出匹配，記mI(s)=|Ms|.記ω(G)表示圖G的分支數(shù)，o(G)表示圖G的奇分支數(shù).

本文主要證明了:設(shè) t1，t2，…，tk是 K 個(gè)正數(shù)，其中是奇數(shù)的ti的個(gè)數(shù)記為l.(1)當(dāng)且僅當(dāng)每個(gè)ti是偶數(shù)時(shí)，MP+Kti)是導(dǎo)出匹配可擴(kuò)圖，其中MP是基數(shù)為P的導(dǎo)出匹配;(2)當(dāng)且僅當(dāng)l≤m－2且l=m(mod2)時(shí)，Km+Kti)是導(dǎo)出匹配可擴(kuò)圖.

引理1(Tutte定理) 圖G中存在完美匹配當(dāng)且僅當(dāng)對(duì)于任意的S?V(G)，有o(G－S)≤|S|，其中o(G－S)表示G－S的奇分支數(shù).

引理2 如果圖G是導(dǎo)出匹配可擴(kuò)圖，則圖G是2－連通的.

由Tutte定理和導(dǎo)出匹配可擴(kuò)圖的定義，可得下面的引理3.

引理3 圖G是導(dǎo)出匹配可擴(kuò)的當(dāng)且僅當(dāng)對(duì)于G的任意導(dǎo)出匹配M和S?V(G)V(M)，有

o(G－V(M)－S)≤|S|.

引理4 圖G是導(dǎo)出匹配可擴(kuò)的當(dāng)且僅當(dāng)對(duì)任意的 S?V(G)，有

o(G －S)≤|S|－2mI(S).

定理 設(shè)t1，t2，…，tk是K個(gè)正數(shù)，其中是奇數(shù)的ti的個(gè)數(shù)記為l.

(1)當(dāng)且僅當(dāng)每個(gè)ti是偶數(shù)時(shí)，MP+(Kti)是導(dǎo)出匹配可擴(kuò)圖，其中MP是基數(shù)為P的導(dǎo)出匹配;

(2)當(dāng)且僅當(dāng)l≤m－2且l=m(mod2)時(shí)，Km+K).ti是導(dǎo)出匹配可擴(kuò)圖

證明 (1)設(shè) t1，t2，…，tk是偶數(shù)，G1=KP，G2=K，G=G+G.設(shè)M是圖G的一個(gè)導(dǎo)出匹配，ti12下面我們將證明M包含在圖G的一個(gè)完美匹配中.顯然，如果M中含E(Gi)的一條邊，則V(M)中的點(diǎn)都不在V(G3－i)中，其中 i=1，2.因此我們分下面三種情形來討論:

情形1E(M)?E(G1).這種情形下，|E(M)|=1，G1－ V(M)同構(gòu)于 MP－1，所以 G1－ V(M)有一個(gè)完美匹配MP－1.由于G2的每一個(gè)分支都是有偶數(shù)個(gè)頂點(diǎn)的完全圖，所以 G2有一個(gè)完美匹配M2.于是，MP－1∪M∪M2就是包含M的G的完美匹配.

情形2E(M)?E(G2).注意到G2的每一個(gè)分支最多包含M中的一條邊，所以，G2－V(M)的每一個(gè)分支仍然是一個(gè)有偶數(shù)個(gè)頂點(diǎn)的完全圖，于是G2－V(M)有一個(gè)完美匹配 M2.因此，MP∪M∪M2就是我們要找的一個(gè)完美匹配.

情形3E(M)是E(G1，G2)的一個(gè)子集，其中E(G1，G2)中每一條邊的頂點(diǎn)一個(gè)在V(G1)中，一個(gè)在V(G2).這種情形下，|V(M)|=1，設(shè) M={υν|υ∈V(G1)，ν∈V(G2)}.設(shè)M1和M2分別是G1和G2的完美匹配，在 M1中 υ匹配 υ＇，在 M2中 ν匹配 ν＇，則(M1{υυ＇})∪(M2{νν＇})∪M∪{υ＇ν＇}是 G 的一個(gè)完美匹配.因此，G=G1+G2是導(dǎo)出匹配可擴(kuò)圖.

反過來，如果某個(gè)ti是奇數(shù)，則MP是G的導(dǎo)出匹配，G－V(M)有一個(gè)分支 Kti.因此，G －V(M)沒有完美匹配，即G不是導(dǎo)出匹配可擴(kuò)圖.

(2)設(shè) l≤m －2 且 l=m(mod2).令 G1=Km，G2=Kti，G=G1+G2.顯然，G 的頂點(diǎn)數(shù)是偶數(shù).設(shè)S是V(G)的子集.如果S不是G的點(diǎn)割，則o(GS)≤1.因?yàn)閛(G－S)和|S|有相同的奇偶性，所以o(G－S)≤|S|－2mI(S).如果S是G的一個(gè)點(diǎn)割，則V(G1)一定是S的子集.注意到，一個(gè)完全圖的最大導(dǎo)出匹配中只有一條邊，如果S=V(G1)，則o(GS)=l≤m－2=|S|－2mI(S).如果 S中有 G2的點(diǎn)且這些點(diǎn)只在G2的一個(gè)分支中，則G［S］是完全圖，因此，o(G －S)≤l+1≤m+1－2≤|S|－2mI(S).

現(xiàn)在，設(shè)S中有G2的點(diǎn)且這些點(diǎn)至少包含在G2的兩個(gè)分支中，如果G［S］有一條邊e在G2的一個(gè)分支中，令 S'=SV(e)，則 o(G － S)=o(G － S＇)，且mI(S)－1≤mI(S＇)≤mI(S)，這就意味著|S'|－2mI(S')≤|S|－2mI(S).設(shè) M 是 G［S∩V(G2)］的一個(gè)最大匹配，S″=SV(M).則G2的每一個(gè)分支最多包含S″的一個(gè)元素.設(shè)r是與S″的交集非空的偶分支的個(gè)數(shù)，則|S″|≥m+r且 mI(S″)=1.因?yàn)?S″可以通過依次刪去M中邊的頂點(diǎn)得到，所以o(G－S)=o(G －S″)≤l+r≤m －2+r≤|S″|－2mI(S″)≤|S|－2mI(S).

由上面的討論可知，G是導(dǎo)出匹配可擴(kuò)圖.

反之，如果l=m(mod2)不成立，則G的頂點(diǎn)數(shù)是奇數(shù)，從而G不是導(dǎo)出匹配可擴(kuò)的.如果l≥m－1，則

o(G－V(G1))=l≥m －1＞m －2=|V(G1)|－2mI(V(G1)).

由定理1，G不是導(dǎo)出匹配可擴(kuò)的.

［1］D.Bauer，H.Broersma，E.Schmeichel.Toughness in

Graphs－A Survey，Graphs Combin.，22(2006)，1－35.［2］J.A.Bondy，U.S.R.Murty.Graph Theory with Applica

tions，London，Macmillan Press Ltd(1976).

［3］X.M.Wang，Z.K.Zhang，Y.X.Lin.Bipartite matching extendable graphs，Discrete Math.，308(2008)，5334 －5341.

［4］X.M.Wang，S.J.Zhou，Y.X.Lin.Bipartite matching extendability and Toughness，submitted.

［5］J.J.Yuan.Induced matching extendable graphs，J.Graph Theory，28(1998)203－213.