關(guān)于連通非完全簡單二分圖的幾個結(jié)論

【摘要】文章主要給出了連通非完全簡單二分圖的幾個結(jié)論，這為進(jìn)一步研究基本極大（m+1）K2free二分圖的結(jié)構(gòu)即為研究基本極大（m+1）K2free二分圖的頂點數(shù)、最大度、連通度和最小度奠定了基礎(chǔ).

【關(guān)鍵詞】導(dǎo)出匹配； 導(dǎo)出匹配數(shù)；基本極大（m+1）K2free二分圖

引言 圖的匹配理論在組合數(shù)學(xué)、運籌學(xué)與控制論中的作用日益突出，近年來更成為圖論及組合最優(yōu)化中更為活躍的核心課題之一，而圖的導(dǎo)出匹配是今年來興起的新的研究方向.二分圖又稱作二部圖，是圖論中的一種特殊模型.本文章主要探討連通非完全簡單二分圖的一些有用的結(jié)論，這為進(jìn)一步研究基本極大（m+1）K2free二分圖的結(jié)構(gòu)奠定了基礎(chǔ).

記號：對一個簡單圖G，記

MIM（G）=max{M：M是圖G的導(dǎo)出匹配且|M|=IM（G）}

定義1 設(shè)G=（V1，V2，E）是一個無向圖，V1，V2是兩個互不相交的頂點集，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個頂點i和j分別屬于這兩個不同的頂點集，則稱圖G為一個二分圖.

定義2 ME是圖G的一個匹配，如果對M中任何不相同的兩邊e，f，都有V（e）∩V（f）=.

定義3 圖G的一個匹配M是導(dǎo)出匹配，如果E（V（M））=M.

定義4 我們稱圖G是一個極大（m+1）K2free二分圖，如果圖G是連通的非完全簡單二分圖，使得對圖G中任何不相鄰的兩點x和y，其中G+xy不含奇圈，都有IM（G+xy）=IM（G）+1=m+1.

主要結(jié)果與證明

定理1 設(shè)G=（V1，V2，E）是一個連通非完全簡單二分圖，其中（V1，V2）是圖G的一個二劃分，設(shè)v0∈V1，N（v0）=V2且E（G-v0）≠，則IM（G）=IM（G-v0）.

定理3 設(shè)G=（V1，V2，E）是一個連通非完全簡單二分圖，G1是G的一個連通子圖.設(shè)x和y是圖G1中不相鄰的兩點，則G+xy為二分圖當(dāng)且僅當(dāng)G1+xy為二分圖.

證明 假設(shè)G+xy不是二分圖，G1+xy是二分圖，則G+xy中有一個包含新加邊xy的奇圈，則G中含一條偶數(shù)條邊的xy路P.由于G1為連通圖，則G1中包含一條xy路Q.由于G1+xy是二分圖，因此Q有奇數(shù)條邊，從P和Q可知G中含有奇圈，與G是二分圖矛盾，定理得證.

定理4 設(shè)G=（V1，V2，E）是具有二劃分（V1，V2）的一個基本極大（m+1）K2free二分圖，那么對于任意兩個相異頂點x1，x2∈V1，都有NG（x2）-NG（x1）≠.

證明 設(shè)IM（G）=m，x1，x2∈V1，并假設(shè)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二分圖.就與給定的條件矛盾.設(shè)x和y是使得G+xy不含奇圈的不相鄰的兩點，且x，y≠x2，令M∈MIM（G+xy）.我們有如下結(jié)論：

斷言：為了證明這個斷言，我們分兩種情形討論：

情形1x2V（M）.在這種情形下，IM（G-x2+xy）=|M|=IM（G+xy）=IM（G）+1=IM（G-x2）+1，斷言成立.

情形2 x2∈V（M）.在這種情形下，設(shè)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得證.

【參考文獻(xiàn)】

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