《圖中因子存在性的局部性條件》是依託北京理工大學，由熊黎明擔任項目負責人的面上項目。
基本介紹
- 中文名：圖中因子存在性的局部性條件
- 依託單位：北京理工大學
- 項目負責人：熊黎明
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
本項目研究圖的因子:哈密爾頓圈、有界定分支個數的2-因子及偶因子、有界定最大度的連通偶因子。本項目研究圖中這些因子存在性的局部性條件，探討它們等價的局部性條件。本項目試圖用k-Hourglass局部性質,P(l,k)局部性質來探討Matthews and Sumner猜想(每個4連通無爪圖是哈密爾頓的)及Saito猜想(每個滿足局部Chvátal-Erd?s條件的圖是哈密爾頓的)並研究每個滿足連通且局部連通的圖是否有一個界定最大度的連通偶因子的問題,從而為圖的因子存在性研究注入新的研究方法與研究內容。 本項目試圖給出能夠處理一般禁用子圖(即不包含二部圖K(1,n)為導出子圖)的局部閉包運算,嘗試將無爪圖的結果拓展到一般圖上。一般來說,上述因子的存在性問題是NP-完全困難的,這表明了本項目的研究意義。本項目致力於尋找能判斷稀疏圖的局部性條件,為研究工作注入新內容。
結題摘要
本項目考慮了圖的因子存在性的局部化條件。本項目分別從圖的因子存在性的禁用子圖條件,疊代線圖的性質原圖刻畫,無爪圖的最小度條件等幾個方面得到了一系列的研究結果。我們考慮了具有界分支個數的偶因子，推廣了一些現有結果，尤其是利用圖的局部性質來刻畫圖的哈密爾頓性，這些結果推廣了現有的關於圖的哈密爾頓性的局部性條件，將禁用子圖與圖的局部性質結合來考慮圖的性質，它推廣了傳統的局部性條件，這方面的結果具有創新性。我們也考慮了疊代線圖的存在界定分支個數的偶因子的原圖特徵刻畫，這個特徵表明我們可以利用原圖來刻畫疊代線圖的界定分支個數的偶因子，避免了高疊代線圖給研究帶來的不便，從而使得我們考慮問題變得更加直接直觀，由此我們得到了一些精確界，這是主要便利的創新之處。我們還利用最小度考慮了無爪圖的哈密爾頓性，解決了目前存在的一些猜想，得到了對於任意的只要最小度不大於它的介的k分之一倍，那么問題可以歸結為考慮有限個頂點的圖是否存在生成閉跡，而這是可以用計算機來計算出來的。而一般問題則是沒有有效算法的。我們的結果發表在圖論頂級雜誌<組合B>上。
