导出匹配可扩图的一些结果

张媛郭静

(郑州铁路职业技术学院，河南 郑州 450052)

本文所讨论的图G都是有限简单无向图。V(G)、E(G)分别表示图G的顶点集和边集，o(G)表示图G的奇分支数.设S⊆V(G)，S的邻集NG(S)={υ|υ∈V(G)S，且存在一点 ν∈S，使得 υν∈E(G)};S 的导出边集 E(S)={υν|υν∈E(G)，且 υ，ν∈S}.设 M⊆E(G)，记 V(M)={υ|υ∈V(G)，且存在ν∈V(G)，使得 υν∈E(G)}.Kn表示有 n个顶点的完全图.图G和H的联合，记为G∪H=(V(G)∪V(H)，E(G)∪E(H))，kG表示G的k个不相交拷贝的联合。图G和H的交记为G+H，它是由G∪H添加上G和H之间所有可能的边得到.设M⊆E(G)，若M中任何两边都没有共同的端点，则称M是图G的一个匹配;若V(M)=V(G)，则称匹配M是图G的一个完美匹配;若匹配M满足E(V(M))=M，则称M是图G的一个导出匹配;若图G的任何一个导出匹配M都包含在图G的一个完美匹配中，则称图G是导出匹配可扩图.设S⊆V(G)，Ms是G［S］中的最大导出匹配，记mI(s)=|Ms|.记ω(G)表示图G的分支数，o(G)表示图G的奇分支数.

本文主要证明了:设 t1，t2，…，tk是 K 个正数，其中是奇数的ti的个数记为l.(1)当且仅当每个ti是偶数时，MP+Kti)是导出匹配可扩图，其中MP是基数为P的导出匹配;(2)当且仅当l≤m－2且l=m(mod2)时，Km+Kti)是导出匹配可扩图.

引理1(Tutte定理) 图G中存在完美匹配当且仅当对于任意的S⊆V(G)，有o(G－S)≤|S|，其中o(G－S)表示G－S的奇分支数.

引理2 如果图G是导出匹配可扩图，则图G是2－连通的.

由Tutte定理和导出匹配可扩图的定义，可得下面的引理3.

引理3 图G是导出匹配可扩的当且仅当对于G的任意导出匹配M和S⊆V(G)V(M)，有

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

引理4 图G是导出匹配可扩的当且仅当对任意的 S⊆V(G)，有

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

定理 设t1，t2，…，tk是K个正数，其中是奇数的ti的个数记为l.

(1)当且仅当每个ti是偶数时，MP+(Kti)是导出匹配可扩图，其中MP是基数为P的导出匹配;

(2)当且仅当l≤m－2且l=m(mod2)时，Km+K).ti是导出匹配可扩图

证明 (1)设 t1，t2，…，tk是偶数，G1=KP，G2=K，G=G+G.设M是图G的一个导出匹配，ti12下面我们将证明M包含在图G的一个完美匹配中.显然，如果M中含E(Gi)的一条边，则V(M)中的点都不在V(G3－i)中，其中 i=1，2.因此我们分下面三种情形来讨论:

情形1E(M)⊆E(G1).这种情形下，|E(M)|=1，G1－ V(M)同构于 MP－1，所以 G1－ V(M)有一个完美匹配MP－1.由于G2的每一个分支都是有偶数个顶点的完全图，所以 G2有一个完美匹配M2.于是，MP－1∪M∪M2就是包含M的G的完美匹配.

情形2E(M)⊆E(G2).注意到G2的每一个分支最多包含M中的一条边，所以，G2－V(M)的每一个分支仍然是一个有偶数个顶点的完全图，于是G2－V(M)有一个完美匹配 M2.因此，MP∪M∪M2就是我们要找的一个完美匹配.

情形3E(M)是E(G1，G2)的一个子集，其中E(G1，G2)中每一条边的顶点一个在V(G1)中，一个在V(G2).这种情形下，|V(M)|=1，设 M={υν|υ∈V(G1)，ν∈V(G2)}.设M1和M2分别是G1和G2的完美匹配，在 M1中 υ匹配 υ＇，在 M2中 ν匹配 ν＇，则(M1{υυ＇})∪(M2{νν＇})∪M∪{υ＇ν＇}是 G 的一个完美匹配.因此，G=G1+G2是导出匹配可扩图.

反过来，如果某个ti是奇数，则MP是G的导出匹配，G－V(M)有一个分支 Kti.因此，G －V(M)没有完美匹配，即G不是导出匹配可扩图.

(2)设 l≤m －2 且 l=m(mod2).令 G1=Km，G2=Kti，G=G1+G2.显然，G 的顶点数是偶数.设S是V(G)的子集.如果S不是G的点割，则o(GS)≤1.因为o(G－S)和|S|有相同的奇偶性，所以o(G－S)≤|S|－2mI(S).如果S是G的一个点割，则V(G1)一定是S的子集.注意到，一个完全图的最大导出匹配中只有一条边，如果S=V(G1)，则o(GS)=l≤m－2=|S|－2mI(S).如果 S中有 G2的点且这些点只在G2的一个分支中，则G［S］是完全图，因此，o(G －S)≤l+1≤m+1－2≤|S|－2mI(S).

现在，设S中有G2的点且这些点至少包含在G2的两个分支中，如果G［S］有一条边e在G2的一个分支中，令 S'=SV(e)，则 o(G － S)=o(G － S＇)，且mI(S)－1≤mI(S＇)≤mI(S)，这就意味着|S'|－2mI(S')≤|S|－2mI(S).设 M 是 G［S∩V(G2)］的一个最大匹配，S″=SV(M).则G2的每一个分支最多包含S″的一个元素.设r是与S″的交集非空的偶分支的个数，则|S″|≥m+r且 mI(S″)=1.因为 S″可以通过依次删去M中边的顶点得到，所以o(G－S)=o(G －S″)≤l+r≤m －2+r≤|S″|－2mI(S″)≤|S|－2mI(S).

由上面的讨论可知，G是导出匹配可扩图.

反之，如果l=m(mod2)不成立，则G的顶点数是奇数，从而G不是导出匹配可扩的.如果l≥m－1，则

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

由定理1，G不是导出匹配可扩的.

［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.