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

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

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

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

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

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

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

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