《圖中最長圈及相關問題的研究》是依託福州大學，由劉清海擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖中最長圈及相關問題的研究
- 依託單位：福州大學
- 項目類別：青年科學基金項目
- 項目負責人：劉清海
項目摘要,結題摘要,
項目摘要
本項目主要研究以下兩個問題：（1）3連通3正則圖G的最長圈的長度的下界，以及該問題在G是平面圖或者不含Petersen-minor或圈4邊連通等條件下的研究. 此研究與Bondy和Jackson猜想密切相關，即：存在一個常數c＞0使得任意一個階數為n的三正則圈4邊連通圖都存在一個圈長度至少為cn.（2）Bermond和Lovász 提出的問題：是否存在一個整數k使得任意k強連通有向圖D以及任意兩個點x,y,都存在一個有向圈包含x和y? Jeager猜想該問題對定向圖在k≤3時成立. 本項目嘗試解決或者部分解決上述問題.
結題摘要
最長圈問題一直以來都是圖論中非常重要且十分困難的問題，項目主要圍繞Thomasson猜想（任意4連通線圖是Hamiltonian的）與Bondy-Jackson猜想（存在一個常數c使得任意圈4邊連通3正則圖存在一個長度至少為cn的圈），研究線圖的最長圈問題。主要證明了任意3連通3正則圖G以及G的任意兩條邊e,f, 都存在一個包含邊e,f且長度至少為n^0.8的圈。研究過程中，發現了一種研究Thomasson猜想的一種新方法，即只要在原圖中能找到一顆支撐樹與一顆與之邊不相交的邊控制樹，則對應的線圖一定是Hamiltonian的，該條件與之前已知的條件（存在兩顆邊不相交的支撐樹）要弱很多，因此項目還研究了邊控制樹的存在性的問題。我們給出了一些存在兩顆邊不相交的邊控制樹的必要條件和充分條件。 同時還從不同的角度給出了邊不相交支撐樹的存在性的一些充分條件，比如用圖的特徵值來刻畫邊不相交支撐樹的存在性等，該結論解決了Ciaba和Wong的一個相關猜想；還給出了存在k個完全獨立支撐樹的充分條件等。此外, 對有向圖，給出了強連通有向圖的度序列的一個刻畫，並且給出一個例子來說明2強連通要比強連通難得多。
