《圖的彩虹連通與廣義連通度》是依託南開大學，由李學良擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的彩虹連通與廣義連通度
- 項目類別：面上項目
- 項目負責人：李學良
- 依託單位：南開大學
中文摘要,結題摘要,
中文摘要
圖的彩虹連通和廣義連通度都是圖的經典連通性概念的自然推廣，對它們的研究是對圖論學科中連通性這一重要分支的新發展，具有重要的理論意義。不僅如此，它們在保密通訊網路的設計和大規模積體電路的設計中都有重要的套用背景。本項目是我們上一研究項目的深入繼續，我們將綜合地運用極值圖論、機率方法、隨機圖論、(近似)算法設計與複雜性分析、以及結構圖論等中的方法和技術，在圖的彩虹連通和廣義連通度這兩個新的研究領域中，發展出深入系統的理論研究方法，解決其中的困難問題和猜想,進一步最佳化它們與其它圖參數之間的不等式關係，創建起有關它們的Erdos-Gallai型、Bollobas型、Nordhaus-Gaddum型、Menger型、 Nash-Williams-Tutte型的結果，從而建立起它們與圖論經典結果和理論的深刻聯繫，以期對圖的連通性和染色理論這兩個圖論學科的經典研究分支做出新貢獻。
結題摘要
四年來，本項目在國家自然科學基金的資助下，在項目組成員的一致努力下，取得了豐富的研究成果，完成了項目預期的各項主要目標。發表論文73篇，其中65篇為SCI檢索期刊，在Springer等出版著作5部、在高教出版譯著1部；培養畢業博士17人、博士後出站5人、碩士1人。 我們的研究工作得到了國際同行學者的廣泛關注，應反映前沿研究專題的數學系列叢書Springer Briefs in Mathematics編輯的邀請撰寫出版2部專著：Generalized Connectivity of Graphs, Springer 2016， 和 Properly Colored Connectivity of Graphs, Springer （審稿通過，2018年出版）。關於圖的彩虹連通數和彩虹連通指標，我們給出圖的彩虹連通數分別依據於獨立數、塊數的緊的上界；利用Szemerédi的正則引理、控制集給出圖的k-彩虹指標依據於最小度的上界。關於圖的正常連通數，給出一類反例否定了Borozand等在Discrete Math雜誌上發表文章中的猜想：對於非完全圖G，如果κ（G） = 2，δ(G) ≥ 3，則有 pc(G) = 2；利用Thomassen的結果證明了Magnant的一個猜想的正確性：對於2-連通的非完全圖，如果diam(G) = 3，δ(G) ≥ 3，則有 pc(G) = 2；同時，對於另一個猜想：如果階為n的非完全連通圖G滿足δ(G) ≥ n/4，則有 pc(G) = 2，證明了它對除了兩個階為7、8的小圖外的所有圖都成立；證明了隨機圖的正常連通數為2。關於圖的廣義連通度，我們解決了關計算複雜性的猜想等。這些結果發表在Discrete Appl. Math., Theoretical Computer Science, Discrete Math., Graphs Combin.,J. Comb. Optim.等雜誌上。 除在圖的彩虹連通數和廣義連通度方面的研究外，我們還在圖的能量和其他能量、圖熵等其他方面做出了重要的研究結果，解決了Cavers等人提出的奇圈圖最大斜譜半徑問題的猜想，以及研究隨機混合圖的譜分布問題，這些結果發表在Electron. J. Combin.， Linear Alg. Appl.等雜誌上，並且出版3部相關專著和撰寫3章相關綜述文章。
