關于連通非完全簡單二分圖的幾個結論

【摘要】文章主要給出了連通非完全簡單二分圖的幾個結論，這為進一步研究基本極大（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.