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

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

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

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

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

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

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