圖中頂點不交的樹、圈和弦圈的存在性

《圖中頂點不交的樹、圈和弦圈的存在性》是依託西安電子科技大學，由喬勝寧擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖中頂點不交的樹、圈和弦圈的存在性
• 項目類別：青年科學基金項目
• 項目負責人：喬勝寧
• 依託單位：西安電子科技大學

中文摘要

子圖存在性問題是圖論中重要的研究內容之一。 而頂點不交子圖的存在性問題是其中一個主要的方向。這一方面的研究更多的是子圖結構類型相同的情況，如圖中包含因子(生成正則子圖)的各種條件的研究.關於子圖結構類型不相同的情況還有許多問題沒有解決。本項目一方面以樹、圈和弦圈為三種基本子圖，深入研究了圖中包含由這三種基本子圖構成的頂點不交子圖的存在性問題；另一方面從圖的剖分角度對圖中包含頂點不交剖分子圖的問題展開深入系統的分析。 重點研究一般圖中頂點不交的樹、圈、弦圈和它們相互組合的頂點不交剖分子圖的存在性問題，給出各種存在性條件，同時設計出相應的智慧型算法。本項目的研究是對於頂點不交的子圖存在性問題的深入發展，具有鮮明的創新性和重要的理論意義。

結題摘要

子圖存在性問題是圖論中重要的研究內容之一。而頂 點不交子圖的存在性問題是其中一個主要的方向。這一方面的研 究更多的是子圖結構類型相同的情況，如圖中包含因子(生成正 則子圖)的各種條件的研究。關於子圖結構類型不相同的情況還 有許多問題沒有解決。本項目就這一課題進行了深入研究，得到了以下結果。一、研究了圖中頂點不交圈、弦圈的存在性問題。 給出了圖中包含頂點不交圈和弦圈的鄰域並條件，同時構造例子表明結論中的條件是最好的。 二、Finkel 得到了圖中包含頂點不交弦圈的最小度條件。注意 到，他的結果中頂點不交的每個圈至少包含一條弦。Wang 對平衡二 部圖研究了類似的問題：給出了平衡二部圖中包含頂點不交弦圈（至 少包含兩條弦）的最小度條件。我們給出了一般圖中包含頂點不交多 弦圈的最小度條件。三、從生成剖分的角度推廣了Dirac關於圖中包含Hamilton圈的 一個經典結論，得到了最小度條件下圈和弦圈生成剖分的存在性。進一步我們從生成圈剖分 的角度將Brandt的結果推廣到任意點不交圈構成的子圖上，事實上， 該結果也是2因子存在性的新結果，從生成剖分的角度給出了2因子的 一個新理解。四、從剖分的角度研究了不相鄰三點度和條件下k個點不交圈的剖分子圖存在性問題。給 出了圖中包含點不交圈的剖分的三點度和條件，同時說明此條件是最好的。五、將 樹、圈和弦圈組合起來，考慮其存在性的最小度條件。得到了如下結 果：令n,r,t是三個整數， H是一個包含n 個頂點 r個非平凡分支的圖， 並且每個分支或者是一棵樹或者是一個單圈圖。如果G是一個包含至 少n+4t個頂點的圖，並且G 的最小度至少是n-r+3t，則G包含H的一個 圈剖分和t個弦圈，所有的都是頂點不交的。以上是本項目的主要研究成果，達到了預期的目標。