收縮臨界6連通圖中6度頂點(diǎn)數(shù)新的下界.pdf

1、對(duì)于F∈V(G)，記NG(F)=(U∞FNG(x))-F設(shè)G是非完全圖，T是最小點(diǎn)割，F(xiàn)是G-T的至少一個(gè)分支但不是所有分支的并，則稱F是G的斷片或T-斷片。F=G-T-F，那么F也是T-斷片。這時(shí)我們稱F，F(xiàn)是T分離G所得的兩個(gè)斷片，若F是斷片，但F的任何真子集都不是G的斷片，則稱F為G的端片階最小的斷片，稱為原子。為方便起見，我們常常將V(F)與F等同起來(lái)。X∈V(G)，G中與x關(guān)聯(lián)的所有邊的集合記為E(x)設(shè)F是圖G一個(gè)斷片，x

2、∈V(G)，如果N(F)包含E(x)中某一條邊的2個(gè)端點(diǎn)，則稱F是一個(gè)E(x)斷片。 如果將k連通圖G中的一條邊e收縮之后所得到的圖是一個(gè)k連通圖，那么這條邊e就叫做G的k可收縮邊，簡(jiǎn)稱可收縮邊1961年Tutte證明了階至少是5的3連通圖有可收縮邊(［15])之后人們對(duì)3連通圖中的可收縮邊進(jìn)行了廣泛的研究，在3連通圖中可收縮邊的分布和可收縮邊條數(shù)的下界等方面都得到了計(jì)多結(jié)果(［4］)對(duì)于k≥4，Thomassen[14]證明了

3、存在無(wú)限多個(gè)k連通k正則圖，這一類圖中不含有k可收縮邊一個(gè)k連通非完全圖G若不含有k可收縮邊，那么G叫做收縮臨界k連通圖。為得到k連通圖中存在可收縮邊的條件，很自然要對(duì)收縮臨界k連通圖(K≥4)進(jìn)行研究。對(duì)于k=4，Martinov[12]清楚地刻畫了收縮臨界4連通圖，即：收縮臨界4連通圖只有兩類：一類是圈的平方，另一類是圖4連通3正則圖的線圖。 當(dāng)k≥5時(shí)，收縮臨界k連通圖的刻畫要困難得多一般地，Egawa[5]證明了每個(gè)收縮

4、臨界k連通圖(K≥4)都存在一個(gè)階至多是K/4的斷片，由此我們知道每個(gè)收縮臨界k連通圖中都有一個(gè)度至多是[5K/4]-1的點(diǎn)。因此，對(duì)于5≤k≤7，每個(gè)收縮臨界k連通圖都有一個(gè)k度點(diǎn)，近午來(lái)人們圍繞收縮臨界k連通圖中k度頂點(diǎn)的分布以及該類圖中k度頂點(diǎn)數(shù)的下界做了大量的工作[2]。 用Vk(G)表示圖G中k度點(diǎn)的集合，Ando等人提出如下問(wèn)題： 問(wèn)題：設(shè)k是一個(gè)整數(shù)且5≤k≤7，對(duì)收縮臨界k連通圖，是否存在一個(gè)常數(shù)ck，使

5、得|Vk|≥ck|V(G)|.若有，試確定CK的最大值?對(duì)于收縮臨界5連通圖，袁旭東在1994年得到：收縮臨界5連通圖中每一個(gè)點(diǎn)都與1個(gè)5度點(diǎn)相鄰，由此可以推出G中至少有1/5|G|個(gè)5度頂點(diǎn)1997年蘇健基進(jìn)一步證叫了：收縮臨界5連通圖中每一個(gè)點(diǎn)都與2個(gè)5度點(diǎn)相鄰。由此可以推出G中至少有2/5|G|個(gè)5度頂點(diǎn)到了2003年，Ando雙重復(fù)得到袁在1994午得到的結(jié)果最近覃城早把以上結(jié)果改進(jìn)到：設(shè)G是收縮臨界5連通圖，則|V5(G)|

6、≥4/9|G|。 對(duì)于k=6，袁旭東和蘇健基在[20]中證明了下面的結(jié)果： 定理A 每個(gè)收縮臨界6連通圖都有兩個(gè)相鄰的6度點(diǎn)。 齊恩鳳，袁旭東對(duì)這一結(jié)果做了如下改進(jìn)： 定理B 設(shè)x是收縮臨界6連通圖中的一個(gè)6度頂點(diǎn)，則或者它與一個(gè)6度頂點(diǎn)相鄰，或者在它的鄰域中存在一點(diǎn)y，在y的鄰域中有兩個(gè)相鄰的6度頂點(diǎn)。 對(duì)于收縮臨界6連通圖，Ando等人證明了以下性質(zhì)： 定理C 設(shè)G是收縮臨界6連通

7、圖，H=G[V6(G)].則對(duì)任一x ∈W，都存在一個(gè)E(x)-斷片A，使得(1)H[N(A)∩V6(G)]()2K2或(2)W(G)∩N(A)={x)，H[N(A)∩V6(G)]()2K2∪K1 利用定理C，Ando等人得到了： 定理D 收縮臨界6連通圖G中至少有|G|7個(gè)6度頂點(diǎn)。 2005年，趙巧鳳和覃城阜等人將這一結(jié)果改進(jìn)為： 定理E 收縮臨界6連通圖G中至少有|G|／5個(gè)6度點(diǎn)。 本文進(jìn)