群連通度和子圖存在性及相關問題的研究

《群連通度和子圖存在性及相關問題的研究》是依託華中師範大學，由李相文擔任項目負責人的面上項目。

基本介紹

• 中文名：群連通度和子圖存在性及相關問題的研究
• 項目類別：面上項目
• 項目負責人：李相文
• 依託單位：華中師範大學

項目摘要

1954年，Tutte教授在研究四色問題時，引進了整數流的概念。四色定理等價於任何平面圖有處處非零4流。後來人們發現整數流問題與圈覆蓋等圖論問題有緊密的關係。1992年, Jaeger教授將整數流的概念推廣為群連通度(group connectivity)，群著色 (group coloring)作為群連通度的對偶提出來。群連通度本身在研究整數流時，有套用價值。Thomassen在1986年提出任何4-邊連通的線圖是Hamilton的。任何超歐拉圖的線圖是Hamilton的。因此，超歐拉圖對研究Thomassen這個猜想有套用價值。超歐拉圖、Hamilton圈的研究 本身就是子圖的存在性問題。本項目的主要內容是：研究群連通度及相關問題， 包括群著色、3-流問題等；研究子圖的存在性, 包括線圖Hamilton性、超歐拉圖等；作為子圖存在性的套用，研究算法的容錯性。

結題摘要

本項目主要研究圖論中整數流、群連通度問題、歐拉子圖的存在即網路容錯性及相關問題，它包括圖的處處非零的3-流問題、群連通度（Group connectivity）、 群著色問題及相關問題。 著名數學家Tutte教授（1954）提出的3-流猜想(Bondy和Murty的《Graph with applications》中未解決問題48):任何4-邊連通圖有非零3-流: 法國數學家 Jeager教授(1992) 把整數流問題推廣到群連通度問題。而群著色問題作為群連通問題的對偶問題提出來的。 平面圖的染色是與平面上的整數流等價。因此， 整數流問題、群連通問題和染色問題是圖論研究的主流問題之一。 我們對對這些問題進行深入、系統的研究，取的一批重要成果。我們刻畫了度條件與群連通性、 度系列與群連通性、禁用子圖與群連通性、平面圖的群著色。因為平面上整數流的問題和染色問題是等價的， 因此我們研究了平面圖的著色以及強邊著色等問題。我們還研究了線圖的Hamilton性、度條件與歐拉連通子圖的存在性, 因子的存在性和網路的容錯性等問題。