3-邊連通基本5-邊連通圖的超歐拉性.pdf

1、圖G中歐拉跡，是G中的一條取G中所有邊的跡。存在歐拉閉跡的圖稱為歐拉圖。如果一個(gè)圖含有生成歐拉子圖，則稱這個(gè)圖具有超歐拉性。
　　 有兩個(gè)關(guān)于這方面的猜想：一個(gè)是1995年Chen和Lai[4]提出每個(gè)3-邊連通，基本5-邊連通的圖都含有生成歐拉子圖；另一個(gè)是Lai[6]提出G為3-邊連通，基本4-邊連通的圖。若σ(G)≥7，則該圖具有超歐拉性。本文首先證明，若圖G最小度δ≥3且σ(G)≥8，則∣E(G)∣≥2∣V(G)∣。然后

2、證明出：G為3-邊連通，基本5-邊連通的圖。若σ(G)≥8，則該圖具有超歐拉性。
　　 下面簡(jiǎn)略訴述證明的思路過程。第一部分：通過Yang[11]的定理，分析得到在δ≥3和σ(G)≥8前提下，只要能保證3度點(diǎn)至少與6點(diǎn)以上的點(diǎn)關(guān)聯(lián)，就可得到∣E(G)∣≥2∣V(G)∣。也就是在保證∣E(G)∣與∣V(G)∣維持一定平衡(滿足∣E(G)∣≥2∣V(G)∣等量關(guān)系)的同時(shí)，去掉與3度點(diǎn)關(guān)聯(lián)的5度點(diǎn)，使得3度點(diǎn)至少與6度點(diǎn)以上的點(diǎn)關(guān)聯(lián)

3、且其他點(diǎn)的度沒有改變，至關(guān)重要的是3度點(diǎn)的個(gè)前后不能改變。反過來思考，5度點(diǎn)至多與五個(gè)3相關(guān)聯(lián)，因而可分五種情況討論。第二部分：通過Nash-Williams∣8∣和Tutte[10]的定理知，要證明圖具有超歐拉性，只需要證明∣S∣≥2(w(G-S)-1)=2(w-1)成立。對(duì)G-S的連通分支進(jìn)行特殊的分類，再在圖G中將這些連通分支都收縮掉。使得收縮后的圖G'滿足∣S∣=∣E(G')∣且w(G-S)=∣V(G')∣。最后結(jié)合第一部分的結(jié)