k連通圖中的k可收縮邊.pdf

1、如果將k連通圖G中的一條邊收縮之后所得到的圖仍然是k連通圖，則稱這條邊為G的k可收縮邊，簡稱可收縮邊.否則稱為不可收縮邊.如果k連通圖中存在可收縮邊，則可使用歸納法去證明k連通圖的某些性質(zhì)，因此研究圖的可收縮邊是很有意義的.在k連通圖中，若邊 xy在一個三角形xyz上，d(x)=k，易見xy不是可收縮邊，圖中這樣的不可收縮邊稱為平凡的不可收縮邊 1961年，Tutte在([1])中證明了階至少是5的3連通圖有可收縮.邊于k≥4，

2、Thomassen在([2])中證明了存在無限多個k連通k正則圖不含k可收縮邊.為得到k連通圖中存在可收縮邊的條件，人人們引進(jìn)了收縮臨界k連通圖的概念.一個不是完全圖的k連通圖稱為收縮臨界k連通圖，如果它的每一條邊都不可收縮容易看出收縮臨界k連通圖的每一個性質(zhì)的否定都是k連通圖中存在可收縮邊的充分條件不難證明沒有收縮臨界1或2連通圖，山Tutte上述證明的結(jié)論知也無收縮臨界3連通圖.收縮臨界4連通圖已被Fontet([3])與Morto

3、nov([4])獨(dú)立地完全刻而：若G是一個沒有可收縮邊的4連通圖，則G或者是一個圈的平方，或者是一個圈4連通3正則圖的線圖.刻而收縮臨界5連通圖要比刻而收縮臨界4連通圖凼難得多，迄今還沒有滿意的結(jié)果，更不用說刻而一般的收縮臨界k連通圖了.當(dāng)前研究k連通圖的可收縮邊的一個重要內(nèi)容是研究收縮臨界k連通圖的性質(zhì)，由此給出k連通圖中存在可收縮邊的一些充分條件： 1981年，Thomassen在([12])中證明了如下定理： 定理

4、A 設(shè)G是一個不含可收縮邊的k連通圖，則G一定含有三角形K3 即，若k連通圖G不含三角形，則G中存在k可收縮邊，Egaw a 等在([5])中計(jì)算了無三角形的k連通圖中可收縮邊的條數(shù)，他證叫了： 定理B 每一個無三角形的k連通圖G，至少有min{|V(G)|+2/3K2-3k，|E(G)|}條可收縮邊 定理B說明了無三角形的k連通圖有相當(dāng)多的可收縮邊.用無三角形的條件來限制收縮邊存在的條件似乎太強(qiáng)了. Egowo

5、在([6])中研究了k連通圖中含有可收縮邊的最小度條件，證明了如下定理： 定理c 設(shè)k≥2是一個整數(shù)，設(shè)G是一個k連通圖，6(G)≥[5K/4]，則G有一條k可收縮邊.除非2≤k≤3，上_GH構(gòu)于Kowarabayashid ([7])中證明了： 若一個圖G沒有了圖同構(gòu)于圖H，我們稱G是H-free圖.K-4表示從K4=中移去一條邊后所得到的圖，Kowar abaya shi 在([7])中證明了： 定理D([

6、7]) 設(shè)k≥3為奇數(shù)，若G為不含K的k連通圖，則G中有可收縮邊 李向軍等對K free k連通圖作了進(jìn)一步的研究，在([8])中得到了K-4 free k連通圖中可收縮邊條數(shù)的一個下界： 定理E ([8]) k≥5為奇數(shù)，G為K free k連通圖，則G有k+1條可收縮邊 三角形在可收縮邊的研究中扮演了一個重要角色 MoJJer在(19中證明了收縮臨界k連通圖中含有很多三角形，他得到了： 定理F (

7、[9]) 設(shè)G是一個收縮臨界k連通圖，則G 中至少有|V(G)|/3個三角形 而最近Kriese肌在([10])中改進(jìn)了M ader 的結(jié)果，他證明了收縮臨界k連通圖中至少有()個三角形 一個boruustie 是指一個山兩個恰有一個公共頂點(diǎn)的三角形構(gòu)成的圖形，最近Ando等人在([11])中得到如下結(jié)果： 定理G 設(shè)k≥4是一個整數(shù)，若一個k連通圖G中沒有可收縮邊，則G中含有boutie 即，若一個

8、k(k≥4)連通圖G中不含boutie，則G中含有可收縮邊。 通過仔細(xì)考察bcnutie free k連通圖，我們在本文第一章中得到如下定理： 定理1 設(shè)G是無boutie 作為了圖，也無H圖作為導(dǎo)出了圖的k連通圖，則G中至少有k條可收縮邊(k ≥4) (圖H=kKl+K2-{uy,vx)+[xy]其中K2=uv，x,y∈(kK1)，即H中有一個圈，該圈恰有一條邊在k 2個三角形上) 我們給出了一個例了

9、，說明定理中的k這個下界是一個較好的下界 定理2 設(shè)G是無boutie，也無(k-2)K1+K2的k連通圖，則G中至少有2k條可收縮邊(k≥4) 本文第二章討論極小k連通圖中含有可收縮邊的禁用了圖條件設(shè)G是k(>2)連通圖，若對任意一條邊e∈E(G)都有G e不再K連通，則稱G為一個極小k連通圖.對k連通圖G，如果G不是極小k連通圖，我們可以在保持k連通性的前提下，通過去掉圖G中的一些邊，直到所得到的圖是極小k連通的，

10、因此每個k連通圖中都有一個極小k連通了圖。顯然如果G是H free，則它的任意一個了圖也是H-free的，另一方面，如果G的k連通了圖含有可收縮邊e，那么e也是G的可收縮邊。 因此討論極小k連通圖中存在可收縮邊的條什是有意義的。 Ando等在([12])中得到了下面的結(jié)論： 定理H 設(shè)G是一個極小k (k≥5)連通圖，不含K1+C4， 任意一個k度點(diǎn)x∈V(G)，E(x)中有一條邊不含在任們?nèi)切沃?，則G中有一條k可收

11、縮邊 對極小k連通圖中的可收縮邊，齊恩風(fēng)等在([13])中證明了，在k≥8時，若極小k連通圖G中不含P=K1+2p3，如果G中任-k度點(diǎn)x，都存在與x關(guān)聯(lián)的不在三角形中的邊，那么G中有k可收縮邊 考察K1+G4，不難發(fā)現(xiàn)，K1+C4b即為 ps+2K1我們在第二章中得到了下面的結(jié)論： 定理3 若極小k (K≥5)連通圖 G中不含Ps+3Ki，G中任意一個k度點(diǎn)x∈V(G)，E(x)中有一條邊不含在任任何三角形中

12、，則G中有一條k可收縮邊 我們構(gòu)造了一個5正則5連通圖，含有K1+C4，但不含p3+3Ki每個5度點(diǎn)關(guān)聯(lián)一條不在三角形上的邊，符合定理3的條件，但不滿足定理H的條件，而容易驗(yàn)證，圖G中有可收縮邊.從這個例了可以看出，用定理3中的條件來限制可收縮邊的存在比用定理H中的條件要好些山定理3，我們自然想進(jìn)一步推廣定理3，我們得到了下面的結(jié)論： 定理4 設(shè)G是不含P3+tK1 的極小k連通圖，G中任意一個k度點(diǎn)x∈V(G)，E