有向超歐拉圖及相關問題研究

《有向超歐拉圖及相關問題研究》是依託福州大學，由洪艷梅擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：有向超歐拉圖及相關問題研究
• 依託單位：福州大學
• 項目類別：青年科學基金項目
• 項目負責人：洪艷梅

項目摘要

歐拉問題是圖論中非常古老的一個問題，一個(有向)圖稱為超歐拉圖是指存在一個(有向)閉跡通過圖中所有點.對無向圖，自Catlin提出約化方法以後超歐拉問題變得非常熱門. 本項目擬研究有向圖上的超歐拉問題，從最小度和連通度充分條件入手，逐步刻畫有向圖的超歐拉性，包括局部結構性刻畫與禁止子圖結構刻畫等, 並給出在這些條件下尋找支撐歐拉子圖的算法. 同時，借鑑Catlin的思想提出適用於有向圖的約化方案，建立有向圖超歐拉問題的一個一般性方法；最後，擬把(有向)圖的超歐拉問題與(有向)圖連通度結合起來，提出支撐(邊/弧)連通度的概念，擬把研究(有向)圖連通度的方法套用到(有向)圖的超歐拉性上面，並研究這兩個問題之間的本質聯繫. 該問題的研究與有向哈密爾頓問題以及無向圖上的超歐拉問題密切相關.

結題摘要

歐拉問題是圖論中十分古老且經典的問題，一個圖稱為超歐拉的如果它包含一個支撐歐拉子圖。由於超歐拉問題提供了Thomasson猜想的一種研究思路，因此倍受大家關注。但是有向超歐拉圖方面的研究相對較少，本項目從最小度條件入手研究有向超歐拉圖的相關問題，主要證明了如果有向圖的最小出度與最小入度的和至少為點數減4，則要么是超歐拉有向圖要么屬於兩類特定的圖類，該結論為有向超歐拉圖的第一個結果，圍繞此條件，我們進一步展開研究，給出了最小度和條件，以及對定向圖也相應給出了存在歐拉因子的充分必要條件，利用該條件可以構造出許多最小度很大但不是超歐拉圖，並且利用正則引理進一步將歐拉因子轉換為支撐歐拉子圖。同時，對獨立數較小的圖也給出了連通度充分條件，該條件解決了Jackson猜想在獨立數為2時的特殊情況。關於最長圈問題，給出了一個3連通3正則圖的最長圈的一個下界。同時還研究了分數支撐樹打包與覆蓋問題與圖譜之間的關係。