收縮臨界5-連通圖的性質.pdf

1、　　如果將 k- 連通圖 G 中的一條邊收縮之后所得到的圖仍然是 k- 連通圖,則稱這條邊為 G 的 k -可收縮邊. 利用階至少為5的3連通圖存在 3 --可收縮邊這一性質,1980年C.Thomassen [13] 使用歸納法統(tǒng)一證明了 Kuratowski 的關于平面圖的三個重要定理. k 連通圖的 k --可收縮邊的存在對圖的某些性質進行歸納證明時有著重要的應用. 自從那時起, 人們對 k 連通圖中的 k- 可收縮邊進行了大量的

2、研究. 不存在 k- 可收縮邊的非完全 k 連通圖稱為收縮臨界 k 連通圖. 由于圖的邊的收縮運算與圖的 Minor 之間的緊密聯系, 對 k 連通圖及收縮臨界 k 連通圖的結構的了解有可能對目前很多人關注的一個問題提供解決的線索. 這個問題是 Hadwiger [3]于 1943 年提出的如下猜想.Conjecture 1 對整數 k (k≥ 1) , 任意 k 色圖都有一個 Kk ？ minor. 要解決 Conjecture

3、 1 非常困難, 目前已知的結果不多. Dirac [25] 證明了任意Hadwiger 猜想的極小反例是 5 連通圖.1947 年 Wagner [14]證明了 Hadwiger 猜想在 k=5 時等價于四色定理. 因此直接證明 k=5 時 Hadwiger 猜想成立就意味著四色定理的一個純粹的數學證明. 從這個角度看, 弄清楚 k=5 時的 Hadwiger 猜想的極小反例是那些 5 連通圖是很有意義的. 與之相關的一個問題是確定m

4、inor 極小的 5 連通圖.我們知道 minor 極小的 3 連通圖是 K4 , minor 極小的 4連通圖是 C6 和 K5 ,而 minor 極小的 5 連通圖是哪些圖目前尚不清楚, 而且要
　　2確定這些圖也比較困難. M.Kriesell [24] 猜想是有下面這些圖. Conjecture 2 每一個5連通圖都有一個minor同構于 K6, K2
　　
　　
　　,2,2,1,C5 ？ K3,

5、 I, I~或 G0 . 其中 I 是二十面體,I~ 是將 I 的某一個頂點的鄰域所導出的圈 abcdea用 abceda 代替所得到的圖.G0 是對 I 作如下運算得到的圖： 設 abcdea 為 I的某一個點 w 的鄰域導出的圈, 將頂點 w 和邊 ab 去掉并連接 a, c 和 a, d ,然后把 b, e 粘合所得到的圖. Conjecture 2 也只是在特殊情形下有一些結果. 對平面圖, Dirac 證明了每一個 5

6、連通平面圖有一個 minor 同構于二十面體.最近,G.FIJAVZ 證明對于射影平面圖, Conjecture 2 成立.另一方面, 我們已知收縮臨界 4 連通圖只有兩種類型, 即
　　
　　I<；WP=3>；Cn (n ≥ 5)和圈 4 邊連通 3 正則圖的線圖, 由此可確定出 minor 極小 4 連通圖. 本 2文試圖通過研究收縮臨界 5 連通圖的性質(5 度點和三角形的分布), 了解一些收縮臨界 5 連通圖

7、的結構, 從這個角度尋找方法確定 minor 極小 5 連通圖. 對收縮臨界 5 連通圖的結構人們還知道的不多, 有關的結果如下.Theorem A [15] 收縮臨界 5 連通圖中每一個點都與一個 5 度點相鄰. 后來, 蘇健基進一步證明了.Theorem B[12] 收縮臨界 5 連通圖中每一個點都與 2 個 5 度點相鄰.
　　
　　
　　2 由 Theorem B 可得收縮臨界 5 連通圖 G 至少

8、有 |G| 個 5 度點.本文對收縮
　　
　　
　　5臨界 5 連通圖中的 5 度頂點的分布進行了研究, 得到以下一些結果首先我們構造了一個收縮臨界 5 連通圖, 說明 Theorem B 中的‘2’這個界是不能再改進, 并且得到了以下定理.定理 1 設 G 是收縮臨界 5 連通圖, x∈V(G) 且 d(x)≥ 8 . x1,x2為與 x 相鄰的 5 度點. 若 x1,x2 ∈ E(G) , 則 x 與 3 個 5

9、 度點相鄰. 用 V5(G)表示 G 中的 5 度點的集合, <；V5(G)>； 表示其在 G 中的導出子圖. 則有.定理2 設 G 是收縮臨界5連通圖. 則 <；V5(G)>； 的每一連通分支至少有4個頂點. 對于收縮臨界5連通圖中5度頂點的數目K.Ando 等人[31]提出了如下問題,問題 1 確定常數 c , 使得每一個收縮臨界 5 連通圖至少有 c|G| 個 5 度點. 由Theorem B 可

10、知 c ≥
　　
　　2
　　
　　. K.Ando 等人在[31]中構造了一個收縮臨界5連
　　
　　5通圖(即本文定理 2 后給出的圖)說明了 c ≤ . 本證明了下面的結果.
　　
　　
　　8
　　
　　
　　13定理 4 設 G 是收縮臨界 5 連通圖, 則 |V5(G)|≥ 4
　　
　　
　　|G| .
　　
　　

11、r>　　9 我們還研究了其它一些情形下收縮臨界 5 連通圖的 5 度點的分布.定理 5 設 G 是收縮臨界 5 連通圖, x, y∈ V(G) 且 x≠ y . 則 G 中任意最長的 x-y 路上至少有 2 個 5 度點.定理 6 設 G 是收縮臨界 5 連通圖,
　　C 是 G的邊割且 C 分 G 為 V1,V2兩部分.設 X 是 V1 中與 C 關聯的點集,
　　Y 是 V2 中與 C 關聯的點集. 則YI V5(