收縮臨界5-連通圖的性質(zhì).pdf

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

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

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

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

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

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

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

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

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

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

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