收縮臨界k連通圖中的原子及階較小的端片.pdf

1、本文主要研究收縮臨界k連通圖，如果將k連通圖G中的一條邊收縮之后所得到了圖仍然是k邊通圖，則稱這條邊為G的k可收縮邊。簡(jiǎn)稱可收縮邊。否則稱為不可收縮邊。1961年Tutte[20]證明了階至少是5的3連通圖有可收縮邊，利用這一結(jié)論Thomassen用歸納法統(tǒng)一證明了平面圖的一些性質(zhì)，由此引發(fā)了人們對(duì)一般k連通圖中可收縮邊的研究。不存在可收縮邊的非完全k連通圖稱為收縮臨界k連通圖。對(duì)于k≥4,Thomassen[19]證明了存在無限多個(gè)k

2、連通k正則圖，這一類圖中不含有k可收縮邊，由于收縮界臨界k連通圖每一個(gè)性質(zhì)的否定都可得到k連通圖中存在k可收縮邊的充分條件，因而研究收縮臨界k連通圖的性質(zhì)是十分有意義的。 對(duì)于收縮臨界k連通圖，Egaur[3]首先證明了： 定理A 若G是收縮臨界k連通圖，則G中原子的基數(shù)不超過k／4. 由這定理A知：若G是收縮臨界的，則G是4連通的，因此收縮界4邊通圖是連通度最小可能的收縮臨界圖。Martinou[13]清楚地刻

3、畫了收縮臨界4連通圖：只有圈的平方C2n(n≥5)及圈4連通3正則圖的線圖這兩類。對(duì)于k=5,6,7,由定理A知每個(gè)收縮臨界k連通圖都有一個(gè)k度點(diǎn)。圍繞該類圖人們進(jìn)行了廣泛的研究。已有了比較好的認(rèn)識(shí)（[21][17][16]等）。但對(duì)于k≥8,收縮臨界k連通圖G卻不一定有k度點(diǎn)。因而對(duì)這類圖研究其原子及階較小的端片是切實(shí)可行的，后來蘇健基［15］推廣了Egaua的結(jié)果： 定理B 若G是收縮臨界k連通圖，則G中存在兩個(gè)不相交的斷片

4、A，B，使得｜A｜＋｜B｜≤k/2. 最近Kriesell([9])進(jìn)一步加強(qiáng)，得到：定理C 每一個(gè)收縮臨界k連通圖G有兩個(gè)不相交的斷片A，B，使得｜A｜＋｜B｜≤2｜k／4｜。 蘇健基在文獻(xiàn)［15］中運(yùn)用定理B證明了： 定理D 設(shè)G是收縮臨界k連通圖，如果＆（G）＝5k/4－1,即k能被4整除，那么G有4個(gè)階為k／4的原子，因而G中至少有4×k/4=k個(gè)最小度點(diǎn)。 蘇猜想定理D中G的原子數(shù)目的下界“4”

5、有可能改進(jìn)到“6”，如果成立，那么［4］中的例子將說明“6”是最好可能的，最近這一猜想已被袁旭東等［18］與Kriesell［9］分別證明： 定理E 設(shè)G是收縮臨界k連通圖，如果＆（G）＝5k/4-1,即k能被4整除，那么G有6個(gè)階為k/4的原子，因而G中至少有6×k/4=3k/2個(gè)最小度點(diǎn)。 對(duì)于收縮臨界k連通圖G，令k=4q+r(0≤r≤3),則q=｜k/4].如果r≠0且G國(guó)有一介原子A的基數(shù)等于q，由定理E人們自

6、然會(huì)問G中是否還有另外原子？對(duì)此本文進(jìn)行了探索。得到： 定理1 設(shè)G是收縮臨界k連通圖。如果＆（G）＝［5k／4］－1且k＝4q＋1,那么G有5個(gè)基數(shù)是q的原子，因而G中至少有5［k/4]=5fq個(gè)最小度點(diǎn)。 設(shè)G是收縮臨界k連通圖。K=4q+r(0≤r≤3),G中原子A的基數(shù)為q－1,那么由定理C知G中有另一個(gè)與A不相交的端片B使得｜B｜≤q+1.對(duì)于這樣的端片B其基數(shù)是否可以再小一些呢？對(duì)此本文得到以下結(jié)果：