收縮臨界5連通圖的5度頂點數(shù)和平凡不可收縮邊數(shù)的新的下界.pdf

1、如果將k連通圖G中的一條邊收縮之后所得到的圖仍然k連通，川稱這條邊為G的k可收縮邊。利用隊至少是5的3連通圖中存在3可收縮邊這一性質(zhì)，_1980年Thomassen使用歸納法統(tǒng)一證明了關(guān)于平面圖的Kuratowski等三個重要定理.自那以來，人們對k連通圖中k可收縮邊進行了大量的研究不存在k可收縮邊的完全k連通圖稱為收縮臨界k連通圖.由于收縮臨界k連通圖每一個性質(zhì)的否定都可得到k連通圖中存在k可收縮邊的允分條什，因而對k連通圖中k可收縮

2、邊進行研究就轉(zhuǎn)化為對收縮臨界k連通圖性質(zhì)的研究。 最先Egowa證明每一個收縮臨界k連通圖有一個基數(shù)小于等于k/4的斷片，由此可推出當k=4，5，6，7時，收縮臨界k連通圖的最小度等于k.已經(jīng)知道不存在收縮臨界3連通圖，收縮臨界4連通圖的結(jié)構(gòu)已經(jīng)完全清楚，它們是兩炎特殊的4正則力，接著自然要想弄清收縮臨界5連通圖的結(jié)構(gòu)，經(jīng)過多年的探索，人們發(fā)現(xiàn)這是一個十分困難的問題.為了弄清收縮臨界5連通圖的結(jié)構(gòu)，首先要了解收縮臨界5連通圖性質(zhì)

3、.山前面Egawa的結(jié)果知道收縮臨界5連通圖至少有一個5度頂點，對于收縮臨界5連通圖中5度頂點的分布，袁旭東在1994年得到： 定理A 收縮臨界5連通圖中每一個點都與1個5度點相鄰。 由此可以推出G中至少有1/5│G│個5度頂點。1997年蘇健基進一步證明了： 定理B 收縮臨界5連通圖中每一個點都與2個5度點相鄰。 由此可以推出G中至少有2/5│G│個5度頂點.到了2003午，Ando又重復得到袁

4、在1994年得到的結(jié)果.對于收縮臨界5連通圖G中5度頂點數(shù)的下界，最近覃城阜改進到： 定理C 設G是收縮臨界5連通圖，則G至少有4/9│G│個5度頂點。 本文進一步得到： 定理1 若G為收縮臨界5連通圖，則G中至少有1/2│G│個5度頂點。 對于收縮臨界k連通圖G，最早Thomassen證明圖中都有三邊形，后來Mader改進到有│G│／3個三邊形，最近Kriesell證明至少有2│G│／3個三邊形

5、山丁收縮臨界5連通圖中有很多三邊形，又有很多5度頂點，因而也會有不少通過5度頂點的三邊形.如果k連通圖的一條邊在三邊形上，并且它所對的頂點是k度頂點，也即這條邊的兩個端點有一個公共鄰點是k度點，這條邊顯然是不可收縮邊，稱為平凡不可收縮邊.Ando研究了收縮臨界5連通圖中平凡不可收縮邊的分布，證明了： 定理D 收縮臨界5連通圖G至少有1/2│G│條平凡不可收縮邊。 他還提出猜想: 猜想收縮臨界5連通圖G至少有2