圖的偶匹配可擴性的若干結論.pdf

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

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

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

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

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

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

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