《圖的超歐拉性質和生成偶子圖的分支數研究》是依託山西大學，由牛兆宏擔任項目負責人的數學天元基金項目。
基本介紹
- 中文名：圖的超歐拉性質和生成偶子圖的分支數研究
- 項目類別：數學天元基金項目
- 項目負責人：牛兆宏
- 依託單位：山西大學
項目摘要,結題摘要,
項目摘要
圖論中的超歐拉問題，即確定一個圖是否包含生成歐拉子圖，是由Boesch、Suffey和Tindel在1977年提出的。Catlin在1988年給出的約化定理是研究此類問題的一個重要工具。項目申請人提出了k-超歐拉圖的概念，即包含至多k個分支的生成偶子圖，並且已經推廣了Catlin的約化定理。本項目擬從以下兩個方面進行研究。首先，在已經得到的k-超歐拉圖收縮方法的基礎上，研究基於度條件、頂點數、邊數等條件的生成偶子圖分支數的界定問題。該問題與界定分支個數的偶因子、線圖的2-因子、旅行售貨員(TSP)等問題密切相關，可望推廣一些已有結果，並在研究方法上有所突破；其次，研究具有小鍵約束條件的超歐拉圖問題和k-超歐拉圖問題，此類問題的已有結果已套用於線圖的哈密爾頓連通性等領域，本項目擬在這些結果的基礎上，適當放鬆約束條件，討論更大範圍圖類上的超歐拉問題，可望推廣已知結果。
結題摘要
本項目主要研究了以下圖的超歐拉性質相關的兩個問題。第一，生成偶子圖分支數的界定問題。針對這個問題，我們完全解決了2-邊-連通圖的生成偶子圖分支數界定問題，證明了如果一個2-邊-連通圖頂點數為n，且不含自環，那么這個圖是⌈(n-2)/3⌉-超歐拉圖，即包含一個分支數不超過⌈(n-2)/3⌉的生成偶子圖，或者是一類反例圖。這個界是最好可能的。套用這個結果，我們研究了邊數條件下生成偶子圖分支數的界定問題，最小度條件下偶因子、線圖的2-因子分支數的界定問題，以及小鍵約束條件下的k-超歐拉圖問題，給出了相應的結果。以上這些結果發表在2014年Discrete Mathematics上。第二，具有小鍵約束條件的超歐拉圖問題。針對這個問題，除了作為第一個問題的套用給出的結果之外，我們在國內外已有結果的基礎上研究了範圍更大的圖類，並得到了一些結果，鑒於討論的情況和反例圖較多，目前還在整理和修改階段。
