《圖中因子存在性的新內容與新方法研究》是依託北京理工大學，由熊黎明擔任項目負責人的面上項目。
基本介紹
- 中文名：圖中因子存在性的新內容與新方法研究
- 依託單位：北京理工大學
- 項目負責人：熊黎明
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
圖的因子存在性是圖論中重要的基本問題，起源於哈密爾頓問題和歐拉問題；這方面問題眾多，出現了許多經典的結論。本項目研究著名的Thomasson猜想（每個4連通線圖是哈密爾頓的）；研究一些新因子存在性問題，主要包括界定分支個數的偶因子、界定最大度的連通偶因子、界定分支個數的2-因子存在性問題等。這些研究內容是經典問題的深化和拓展。一般來說，這些因子存在性問題在算法上是NP-完全的，從算法設計角度是沒有解的（除非P=NP）。因此這些問題的研究既有重要理論意義也有實際意義。. 本項目研究上述因子存在性問題的經典度條件(Dirac型、Ore型、Fan型)、連通度條件、禁用子圖條件，還將研究新型條件-支健條件；研究禁用子圖的正反問題；研究圖的收縮方法及閉包運算，可望在方法上有所突破；我們將尋求最好可能的條件，對圖的極值理論具有重要理論價值。. 本項目預計解決一些因子存在性公開問題。
結題摘要
在我們的優勢研究課題---哈密爾頓指數方面, 我們利用在之前的研究項目獲得的哈密爾頓疊代線圖的特徵刻畫基礎上, 得到了確定一個圖的哈密爾頓指數是NP-完全困難的結論, 這進一步說明了我們在這方面研究內容的重要性與困難性。 這方面我們得到了一些哈密爾頓指數的上,下確界, 而且也研究了與哈密爾頓指數相關的哈密爾頓連通指數, 2-因子指數, 偶因子指數的上確界及它們之間的一些關係; 我們也得到了超歐拉指數的穩定性的結論。同時我們也定義了新的閉包運算, 證明了偶因子在這個新的閉包運算下是穩定的結論, 並且將它套用在無爪圖的哈密爾頓圈的存在性方面; 我們將生成歐拉子圖的存在性研究推廣為具有歐拉分支的偶因子存在性研究上, 得到了Catlin發明的收縮方法在具有界定分支個數的偶因子存在性研究上的有效套用,並且得到了一些基本結果, 相信它將在研究類似問題上會得到更多的套用; 在有界定度的連通偶因子研究方面, 我們也獲得了一些開創性的研究結果, 擴展了一些已知結果; 我們的研究內容也涉及到圖的生成跡存在性問題; 在哈密爾頓圈存在性方面,我們也獲得了一些研究成果:一方面我們利用新的條件---局部不連通的頂點滿足它在一個有界定非奇異邊導出圈的條件來研究無爪圖的哈密爾頓圈的存在性,同時也用來研究無爪圖2-因子的存在性。 首次利用邊在小圈上的條件來研究無爪圖的2-因子存在性, 也得到了一些結果; 利用支健條件得到了使得線圖有界定分支個數的2-因子存在性條件; 我們也給出了Thomassen猜想等價猜想:我們得到這個猜想等價於對於任意的正整數k, 具有k單圈性質的4連通的圖是哈密爾頓的; 我們給出了圖的兩個運算, 使得它的線圖2-因子存在性在這兩個運算下保持不變, 並將這個套用於無爪圖的2-因子存在性方面的研究, 得到了更加廣泛的2-因子存在性條件; 我們考慮了著名的Chvátal-Erdös條件的弱化問題: 通過界定最大獨立集合的個數弱化了Chvátal-Erdös條件(保證原來的結論依然成立)。
