局部半完全有向圖的分解及相關問題的研究

《局部半完全有向圖的分解及相關問題的研究》是依託山西大學，由李瑞娟擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：局部半完全有向圖的分解及相關問題的研究
• 項目類別：青年科學基金項目
• 項目負責人：李瑞娟
• 依託單位：山西大學

項目摘要

有向圖（特別是競賽圖及其推廣圖）的分解是圖論的一個重要研究課題。對競賽圖的分解及其相關問題，人們已經取得了許多突破性的成果。局部半完全有向圖是競賽圖的最重要的一類推廣圖，在近二十年得到了廣泛關注。但因其結構的複雜性，許多有關競賽圖的結論還沒有推廣到這個圖類上，許多關於分解的公開問題還沒有得到解決。本項目將系統研究局部半完全有向圖的若干重要分解及相關問題，包括弧不相交的圈路的存在性和強連通生成子有向圖分解等問題，並對Bang-Jensen等人在2012年提出的下面猜想取得實質性進展：“每個3強連通的局部競賽圖包含兩個弧不相交的哈密爾頓圈”和“如果k弧強連通的局部半完全有向圖的最小半度足夠大，那么它包含k個弧不相交的強連通生成子有向圖。

結題摘要

有向圖（特別是競賽圖及其推廣圖）的分解是圖論的一個重要研究課題。本項目研究了競賽圖的一類推廣圖——局部半完全有向圖的分解及相關問題。通過研究局部半完全有向圖的某些圖指標，包括連通度、通用弧、競爭圖等，部分解決了Bang-Jensen和Huang在2012年提出的猜想：“每個3強連通的局部競賽圖包含兩個弧不相交的哈密爾頓圈。”並利用類似的方法，對某些競賽圖的推廣圖，包括多部競賽圖、超競賽圖，k準傳遞有向圖等的競爭圖、二次外鄰、哈密爾頓路等問題進行了研究，將競賽圖的相關結論推廣到了這些圖類上。共發表論文13篇，其中8篇發表在SCI收錄期刊。培養了6名碩士研究生，另有2名在讀研究生。