关于连通非完全简单二分图的几个结论

【摘要】文章主要给出了连通非完全简单二分图的几个结论，这为进一步研究基本极大（m+1）K2free二分图的结构即为研究基本极大（m+1）K2free二分图的顶点数、最大度、连通度和最小度奠定了基础.

【关键词】导出匹配； 导出匹配数；基本极大（m+1）K2free二分图

引言 图的匹配理论在组合数学、运筹学与控制论中的作用日益突出，近年来更成为图论及组合最优化中更为活跃的核心课题之一，而图的导出匹配是今年来兴起的新的研究方向.二分图又称作二部图，是图论中的一种特殊模型.本文章主要探讨连通非完全简单二分图的一些有用的结论，这为进一步研究基本极大（m+1）K2free二分图的结构奠定了基础.

记号：对一个简单图G，记

MIM（G）=max{M：M是图G的导出匹配且|M|=IM（G）}

定义1 设G=（V1，V2，E）是一个无向图，V1，V2是两个互不相交的顶点集，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图.

定义2 ME是图G的一个匹配，如果对M中任何不相同的两边e，f，都有V（e）∩V（f）=.

定义3 图G的一个匹配M是导出匹配，如果E（V（M））=M.

定义4 我们称图G是一个极大（m+1）K2free二分图，如果图G是连通的非完全简单二分图，使得对图G中任何不相邻的两点x和y，其中G+xy不含奇圈，都有IM（G+xy）=IM（G）+1=m+1.

主要结果与证明

定理1 设G=（V1，V2，E）是一个连通非完全简单二分图，其中（V1，V2）是图G的一个二划分，设v0∈V1，N（v0）=V2且E（G-v0）≠，则IM（G）=IM（G-v0）.

定理3 设G=（V1，V2，E）是一个连通非完全简单二分图，G1是G的一个连通子图.设x和y是图G1中不相邻的两点，则G+xy为二分图当且仅当G1+xy为二分图.

证明 假设G+xy不是二分图，G1+xy是二分图，则G+xy中有一个包含新加边xy的奇圈，则G中含一条偶数条边的xy路P.由于G1为连通图，则G1中包含一条xy路Q.由于G1+xy是二分图，因此Q有奇数条边，从P和Q可知G中含有奇圈，与G是二分图矛盾，定理得证.

定理4 设G=（V1，V2，E）是具有二划分（V1，V2）的一个基本极大（m+1）K2free二分图，那么对于任意两个相异顶点x1，x2∈V1，都有NG（x2）-NG（x1）≠.

证明 设IM（G）=m，x1，x2∈V1，并假设NG（x2）-NG（x1）=.对G-x2中每一对不相邻的顶点x和y， G+xy不含奇圈，如果能够证明IM（G-x2+xy）=IM（G-x2）+1成立，则G-x2也是一个极大（IM（G-x2）+1）K2free二分图.就与给定的条件矛盾.设x和y是使得G+xy不含奇圈的不相邻的两点，且x，y≠x2，令M∈MIM（G+xy）.我们有如下结论：

断言：为了证明这个断言，我们分两种情形讨论：

情形1x2V（M）.在这种情形下，IM（G-x2+xy）=|M|=IM（G+xy）=IM（G）+1=IM（G-x2）+1，断言成立.

情形2 x2∈V（M）.在这种情形下，设x2x3∈E（M），令M1=M-x2x3+x1x3，那么M1∈MIM（G-x2+xy），从而IM（G-x2+xy）=IM（G+xy）=IM（G）+1=IM（G-x2）+1.断言成立，因此定理4得证.

【参考文献】

[1] X.X.Song.Induced mathing number of a cubic graph and some forbidden graphs of XC，to appear.

[2] Y.T.Xie and X.X.Song.Basic maximal 2K2free graphs.Joural of Zheng Zhou University，40（4），2008，27-29.

[3]X.X.Song.Basic maximal（m+1）K2free graphs， to appear.

相关热词搜索： 几个 连通 结论 简单