《基於圖的不變數與子圖結構的譜極值問題研究》是依託鄭州大學，由劉瑞芳擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於圖的不變數與子圖結構的譜極值問題研究
- 項目類別：青年科學基金項目
- 項目負責人：劉瑞芳
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
圖譜理論主要通過研究圖的相關矩陣的譜性質來反映圖的結構性質，是當前代數圖論和組合矩陣論共同關注的一個重要課題。本項目擬對圖的譜極值問題開展兩方面的深入研究。第一，基於圖的不變數的譜極值問題：即刻畫圖的不變數固定的圖類中譜參數的極值或極圖，研究圖的特徵值與各種不變數(如團數、色數、獨立數、直徑等)之間的聯繫。圖的特徵值具有好算法，而圖的某些不變數如獨立數及團數的計算是NP-困難的，因此這方面的研究是很有必要的。第二，基於子圖結構的譜極值問題：即確定包含或者禁用某種子圖(如完全子圖、完全二部子圖、給定長的路和圈、Hamilton圈和路等)的圖類中譜參數的極值，如譜形式的Turán型和Zarankiewicz型問題，研究圖的特徵值與某種子圖存在性之間的關係。本項目將綜合運用圖論和矩陣論方法，採用理論推導和計算機驗證相結合的研究方案，挖掘和豐富譜圖論研究的工具，以期推動上述問題的順利解決。
結題摘要
圖譜理論是圖論研究中一個非常活躍而又重要的研究領域，它在量子化學、統計力學、通信網路、計算機科學、圖像處理和模式識別中均有著廣泛的套用。圖譜理論主要通過研究圖的相關矩陣的譜性質來反映圖的結構性質，是當前代數圖論和組合矩陣論共同關注的一個重要課題。譜極值問題是近年來圖譜理論的研究熱點。作為極值圖論的譜拓展，它主要研究圖的各種矩陣表示的極端譜參數。本項目對圖的譜極值問題開展了兩方面的深入研究。第一，基於圖的結構參數的譜極值問題：即刻畫圖的結構參數固定的圖類中譜參數的極值或極圖，研究了圖的特徵值與圖的各種結構參數之間的關係。第二，基於子圖存在性的譜極值問題：即確定包含或者禁用某種子圖的圖類中譜參數的極值。受本項目資助，共發表SCI論文14篇。本項目的代表性成果如下：(1) 刻畫了懸掛點數固定的非二部單圈圖中無符號拉普拉斯最小根達到最小的唯一極圖；(2) 在符號矩陣的意義下，刻畫了懸掛點數固定的非奇異混合圖中第一特徵根達到最小的唯一極圖；(3) 分別提供了二部圖和一般圖含有Hamilton圈和Hamilton路的鄰接譜半徑和無符號拉普拉斯譜半徑條件。總之，本項目的兩方面研究任務與國內外譜極值理論的前沿領域有著密切的聯繫，具有重要的理論研究意義和廣泛的套用價值。
