分數(shù)因子臨界圖及其相關(guān)性質(zhì)的研究.pdf

1、本文所考慮的圖都是簡單無向圖．設(shè)G=(V(G)，E(G))是一個圖，其中V(G)和E(G)分別表示G的頂點集合和邊集合．頂點x在G中的度記為dG(x)，δ(G)表示G中所有頂點度的最小值．對于任意的集合S(￠)V(G)，由S導出的G的子圖記為G[S]，G-S表示由V(G)＼S導出的子圖．用o(G-S)和i(G-S)分別代表G-S中奇分支的個數(shù)和孤立頂點的個數(shù)． 設(shè)g(x)≤f(x)是定義在V(G)上的兩個非負整數(shù)值函數(shù)，H是G的

2、一個支撐子圖．如果對于任意的x∈V(G)，滿足g(x)≤dH(x)≤f(x)，則稱H是G的一個(g，f)-因子．類似的，如果對于任意的x∈V(G)，滿足g(x)=f(x)，則稱日是G的一個f-因子(或g-因子)；如果對于任意的x∈V(G)，有g(shù)(x)=a，f(x)=6且a，b是兩個正整數(shù)，那么(g，f)-因子就可被稱為[a，b]-因子．特別的，對于任意的x∈V(G)，有g(shù)(x)=f(x)=1時，(g，f)-因子就變成了1-因子，即完美匹

3、配． 設(shè)g(x)≤(x)是定義在V(G)上的兩個非負整數(shù)值函數(shù)，h(e)∈[0，1]是-個定義在E(G)上的函數(shù)并且dhG(x)=∑e∈Exh(e)，其中Ex={xy：xy∈E(G)}．此時dhG(x)被稱為是在h作用下的G中頂點x的分數(shù)度，h被稱為是一個指示函數(shù)(inditor fullction)．如果對于任意的x∈V(G)，有g(shù)(x)≤dhG(x)≤f(x)，設(shè)Eh={e：e∈E(G)，h(e)≠0}且Gh是G的一個支撐子

4、圖并使得E(Gh)=Eh，那么Gh就是G的一個分數(shù)-(g，f)-因子．同樣的方法可以類似的定義分數(shù)-k-因子、分數(shù)-[a，b]-因子等．特別的，對于任意的x∈V(G)，有g(shù)(x)=f(x)=1時，分數(shù)-(g，f)-因子變?yōu)榉謹?shù)-1-因子，即分數(shù)完美匹配． 圖的因子理論是圖論中研究的主要問題之一．對因子理論的研究在一個多世紀以前就開始了，但直到上世紀七十年代才逐漸地活躍了起來．到目前為止，對圖的因子方面的研究已經(jīng)得到了不少成果．分

5、數(shù)圖論是相對年輕的分支，因此仍有許多問題有待解決． 本文共分為六大部分，第四部分和第五部分是整個文章的核心，通過分析證明得出了分數(shù)因子臨界圖和分數(shù)-(r，k)-可擴圖的一些結(jié)論． 第一部分是全文的基礎(chǔ)部分．簡要介紹了文中所涉及的概念、術(shù)語和符號，回顧了圖論及圖因子問題的發(fā)展史，并對圖因子問題中常用的重要參數(shù)作了詳細介紹． 第二部分概括總結(jié)了圖因子存在性問題中整數(shù)因子和分數(shù)因子已有的重要定理． 第三部分分析

6、概括出圖因子存在性問題中的兩種常用研究方法． 第四部分重點研究了分數(shù)因子臨界圖(設(shè)G是一個圖，若對于頂點集合V(G)的任意n-子集T使得G-T有分數(shù)-r-因子，則稱G是-個分數(shù)-(r，n)-因子-臨界圖)的一些性質(zhì)，得出了以下結(jié)論： 設(shè)G是δ(G)≥r+n的圖且孤立韌度I(G)≥r+n-1/r．則G是一個分數(shù)-(r，n)-因子-臨界圖． 假設(shè)G是δ(G)≥r+n的圖．若G是分數(shù)-(r，n)-因子-臨界圖，則G也是

7、分數(shù)-(r,n-1)-因子-臨界圖． 如果對于任意的u∈V(G)，G-{u}-有分數(shù)-r-因子，那么G同樣也有分數(shù)-r-因子．第五部分主要研究了分數(shù)-(r,k)-可擴圖(設(shè)G是一個圖，如果對于V(G)的任意r-子集T，G-T是一個分數(shù)-k-可擴圖，則G是一個分數(shù)-(r，k)-可擴圖)的一些性質(zhì)，得出了以下結(jié)論： 圖G是一個分數(shù)-(r，k)-可擴圖當且僅當對于任意的集合U∈V(G)，有i(G-U)≤U-2K-r．其中，|U

8、|≥2k+r且G[U]包含一個k-匹配． 任意—個分數(shù)-(r，k)-可擴圖同時也是—個分數(shù)一(r1，k1，)-可擴圖，其中0≤r1≤r，0≤k1≤k. 設(shè)G是—個圖．則G是—個分數(shù)-(r，k)．可擴圖當且僅當對于G任意的一個i-匹配M(0≤i≤k)，G-V(M)是一個分數(shù)-(r，k-i)-可擴圖． 一個分數(shù)-(r，k)-可擴圖是分數(shù)-(k+r/2)-可擴的． 第六部分是對全文的一個總結(jié)以及對下一步工作的展