k可擴(kuò)圖和n因子臨界圖的等價(jià)及其性質(zhì).pdf

1、令G為一連通圖，其頂點(diǎn)個(gè)數(shù)為v，整數(shù)0≤k≤v／2-1，若G有大小為k的對(duì)集，且G的每一個(gè)大小為k的對(duì)集都包含在G的一個(gè)完美對(duì)集中，則稱G為k可擴(kuò)的．若0≤n≤v-2，對(duì)于圖G的任意大小為佗的頂點(diǎn)子集S(∪)V(G)，G—S均有完美對(duì)集，則稱圖G為n因子臨界的． 本文主要研究k可擴(kuò)圖和n因子臨界圖． 我們注意到對(duì)集可擴(kuò)理論與連通度理論之間有很多的相似的結(jié)論，這促使我們研究k可擴(kuò)圖和尼連通圖之間的關(guān)系．在本文第2章中，我們

2、獨(dú)立地得到了k可擴(kuò)二部圖和k強(qiáng)連通有向圖之間的等價(jià)關(guān)系．利用這個(gè)等價(jià)關(guān)系，我們列舉說明了對(duì)集可擴(kuò)理論和連通度理論的一系列相似結(jié)論，簡(jiǎn)化了k可擴(kuò)二部圖一個(gè)結(jié)論的證明．對(duì)于有完美對(duì)集但非1可擴(kuò)的二部圖，我們證明了其基本分支與有向圖的強(qiáng)連通分支對(duì)應(yīng)．從所得到的等價(jià)關(guān)系，我們還證明了k可擴(kuò)二部圖，k強(qiáng)連通有向圖與組合矩陣的關(guān)系． k可擴(kuò)圖和n因子臨界圖是兩個(gè)關(guān)系密切的概念．因此有不少研究這兩個(gè)圖類之間關(guān)系的工作．由定義即可知一個(gè)2k因子

3、臨界圖總是k可擴(kuò)的．但是反過來，尼可擴(kuò)圖在何種條件下是2k因子臨界的，這是一個(gè)還沒有研究清楚的問題．Favaron和Yu在這個(gè)問題上分別得到了一些結(jié)論．Lou和Yu證明了當(dāng)k≥v／4時(shí)，k可擴(kuò)非二部圖G的連通度k≥2k．這個(gè)連通度達(dá)到了2k因子臨界圖連通度的下界．這啟發(fā)我們研究k≥v／4的k可擴(kuò)圖和2k因子臨界圖的關(guān)系．本文第3章給出我們的研究結(jié)果，即當(dāng)k≥(v+2)／4時(shí)，尼可擴(kuò)非二部圖是2k因子臨界的．我們還給出例子，說明這個(gè)下界是

4、最好可能的．作為一個(gè)推廣，我們還得到了(2k+1)因子臨界圖與k1/2可擴(kuò)圖之間的類似關(guān)系．對(duì)于k=v／4的情況，我們也把k可擴(kuò)圖和2k因子臨界圖的關(guān)系研究清楚，給出了一個(gè)k可擴(kuò)圖是2k因子臨界圖的充分必要條件． 基于我們關(guān)于k可擴(kuò)圖和n因子臨界圖的等價(jià)性質(zhì)的研究結(jié)果，我們可以從系統(tǒng)的角度看待k強(qiáng)連通圖，k可擴(kuò)二部圖，k可擴(kuò)圖和n因子臨界圖，這將有利于我們今后研究工作的開展． 從第4章起我們研究k可擴(kuò)圖和n因子臨界圖的性

5、質(zhì)． 第4章把Anachuen和Caccetta的關(guān)于k可擴(kuò)圖中獨(dú)立數(shù)的一個(gè)結(jié)論推廣到n因子臨界圖． 在第5章的研究工作中，我們?cè)噲D證明k≥v／4時(shí)，k可擴(kuò)圖中有對(duì)集交錯(cuò)的Hamilton圈．我們的工作表明，對(duì)集交錯(cuò)的Hamilton圈的存在性可以由更弱的條件得到．我們證明了在具有完美對(duì)集M的二部圖G中，當(dāng)頂點(diǎn)最小度δ≥v／4+1時(shí)，圖G有M交錯(cuò)的Hamilton圈．在一般圖中，當(dāng)G的連通度k≥v／2時(shí)，除非G屬于一類例

6、外的圖類，G有M交錯(cuò)的Hamilton圈．由于例外圖類不是k可擴(kuò)的，因此從我們的結(jié)論可以推出當(dāng)k≥v／4時(shí)，k可擴(kuò)圖中有對(duì)集交錯(cuò)的Hamilton圈．本章中關(guān)于一般圖的結(jié)論證明有一定的難度，最終的結(jié)論具有與經(jīng)典的Hamilton圈存在性條件類似的簡(jiǎn)潔形式． 在第6章中，我們首先研究了Harary圖及其變種的因子臨界性和可擴(kuò)性，其意義在于這些圖類包含了邊數(shù)最少的k可擴(kuò)圖和n因子臨界圖．我們發(fā)現(xiàn)現(xiàn)有文獻(xiàn)所構(gòu)造的邊數(shù)最少的k可擴(kuò)圖都是