圖的偶匹配可擴(kuò)性的若干結(jié)論.pdf

1、本文所涉及的圖均為無向、簡單有限圖。本文研究了圖論中與圖的偶匹配可擴(kuò)性有關(guān)的一些問題,由以下四部分組成:
　　(1)介紹匹配理論,及匹配可擴(kuò)圖研究的進(jìn)展情況。
　　(2)2k點可刪和k邊可刪的BM-可擴(kuò)圖的度條件。
　　(3)Harary圖的偶匹配可擴(kuò)性。
　　(4)k-偶匹配可擴(kuò)圖。匹配理論是圖論的一個中心研究內(nèi)容之一,也是一個具有生機(jī)和活力的研究領(lǐng)域。它不僅具有很強(qiáng)的應(yīng)用背景,而且還包含著相當(dāng)內(nèi)容豐富而深刻的

2、理論問題,尤其是最近幾十年,對組合論中諸多理論的發(fā)展起了很大作用,它是發(fā)展新的和更一般的組合方法的催化劑。從技術(shù)角度看,匹配問題處于一個難度適中的水平-它們中的多數(shù)問題是可解的,但是解決它們又需要非平凡的技術(shù)方法。Cameron[4]在1989年提出了導(dǎo)出匹配的概念。稱圖G的匹配M是導(dǎo)出匹配,如果M及其關(guān)聯(lián)的頂點構(gòu)成一個導(dǎo)出子圖。關(guān)于導(dǎo)出匹配的研究已得到了豐富的結(jié)果[4,5,6,11,16]。原晉江于1998年首次提出導(dǎo)出匹配可擴(kuò)圖的概

3、念[40]。稱圖G是導(dǎo)出匹配可擴(kuò)的,如果G的每一個導(dǎo)出匹配都可以擴(kuò)充為G的完美匹配。在k-可擴(kuò)圖、導(dǎo)出匹配可擴(kuò)圖和k-因子臨界圖的研究工作基礎(chǔ)上,考慮到非偶圖匹配問題與偶圖匹配問題有本質(zhì)差別的事實,王秀梅[33]在2005年提出另外一個新的概念-偶匹配可擴(kuò)圖。
　　稱圖G的匹配M是偶匹配,是指M關(guān)聯(lián)的頂點集在G中的導(dǎo)出子圖是偶圖.稱圖G是偶匹配可擴(kuò)的(簡稱BM-可擴(kuò)的),是指G的每一個偶匹配都可以擴(kuò)充為G的一個完美匹配。顯然,BM

4、-可擴(kuò)圖一定有偶數(shù)個頂點;完全圖K2m和完全偶圖Km,m是BM-可擴(kuò)的,但是Km,m刪去任意一條邊得到圖不是BM-可擴(kuò)的;僅有的BM-可擴(kuò)路和圈分別是P2和C4。
　　進(jìn)一步,可以看到BM-可擴(kuò)圖和其他匹配可擴(kuò)的關(guān)系很密切。本學(xué)位論文主要做了以下工作。稱圖G是2k-點可刪的BM-可擴(kuò)圖,如果對于V(G)的任意滿足S=2k的子集S均有G—S是BM-可擴(kuò)圖.我們得到:若圖G是簡單連通圖,V(G)=2n,且n≥3.如果δ(G)≥(3n+

5、k)/2,則圖G是2k-點可刪的BM-可擴(kuò)圖.其中k是一個小于等于n-2正整數(shù)。另外[(3n+k)/2]是最小的正整數(shù)δ,使得對于δ(G)≥δ的圖G均是2k點可刪的偶匹配可擴(kuò)圖。稱圖G是k邊可刪的BM-可擴(kuò)圖,若圖G是2n個頂點的簡單連通圖,且對于E(G)的任一滿足|F|=k的子集F,均有G-F是BM-可擴(kuò)圖。我們得到:若圖G是2n個頂點的簡單連通圖,如果δ(G)≥[(3n)/2]+[k/2],則圖G是k邊可刪的BM-可擴(kuò)圖,其中n≥3

6、,且[k/2]≤[(3n)/4]-1。
　　進(jìn)一步我們證明了若圖G是具有2n個頂點的(n-1)邊可刪的BM-可擴(kuò)圖,則g(G)=3,其中n≥2.對于Harary圖的偶匹配可擴(kuò)性我們得到了下列結(jié)論。對于任意的n,H1,2n是BM-可擴(kuò)圖;對于任意的n>1,H2,2n僅當(dāng)n=2時是BM-可擴(kuò)圖;對于任意的n>1,僅當(dāng)n=2,3時H3,2n是BM-可擴(kuò)圖;對于任意的n(n≥3),H4,2n均不是BM-可擴(kuò)圖;對于任意的n(n≥3),當(dāng)n

7、=3,4時,H5,2n是BM-可擴(kuò)圖;當(dāng)n≥5時H5,2n不是BM-可擴(kuò)圖;對于任意的n(n≥3),當(dāng)n=4,5,6時,H6,2n是BM-可擴(kuò)圖。稱圖G是k-偶匹配可擴(kuò)圖,如果G的每個基數(shù)為k的偶匹配都可以擴(kuò)充為G的完美匹配,其中1≤k≤1/2(|V(G)|-2)。
　　對于k-偶匹配可擴(kuò)圖我們有下列結(jié)論:當(dāng)n≥2時,C2n×P2是2-偶匹配可擴(kuò)圖,其中C2n為2n個頂點的圈,P2為兩個頂點的路;設(shè)G是n個頂點的簡單連通圖,且任何