4連通圖中最長圈上的可去邊

徐 麗 瓊

(集美大學理學院，福建廈門361021)

?

4連通圖中最長圈上的可去邊

徐 麗 瓊

(集美大學理學院，福建廈門361021)

摘要：圖的可收縮邊與可去邊是研究連通圖的構造和使用歸納法證明連通圖的一些性質的有力工具.利用邊點割斷片的性質給出了某類4連通圖中在特定子圖上可去邊的分布情況,證明了若4連通圖G的邊點割原子的頂點數大于2,則G中的最長圈C上至少有3條可去邊.

關鍵詞：4連通圖;可去邊;邊點割原子

1背景及定義

我們僅考慮有限簡單圖,若無特別說明,有關圖論的符號和術語見文獻[1].

圖的可收縮邊與可去邊是研究連通圖的構造和使用歸納法證明連通圖的一些性質的有力工具.1961年Tutte[2]首先利用3連通圖中存在可收縮邊的性質給出了3連通圖的一個出色的構造方法.3連通圖存在可收縮邊的一個著名的應用是由Thomassen[3]在1981年給出.他通過歸納法,用統一的方法簡潔明了地證明了關于平面圖的3個著名定理,即1) Kuratowski定理:圖G是可平面的當且僅當G不含同胚于K5或K3,3的子圖;2) Fary定理:每個平面圖有平面的線性表示;3) Tutte定理:每個3連通平面圖有平面的凸表示.在這之前,上述3個定理的證明都比較繁瑣.

關于3,4,5連通圖的可去邊的性質和分布的一些結果見文獻[4-11].我們主要研究4連通圖的可去邊,下面先給出k連通圖(k≥3)中可去邊的定義.

設e是k連通圖G的一條邊,G?e表示圖G做下列運算所得的圖:

(i) 從G中去掉e得圖G-e;

(ii) 如果e的某個端點在G-e中度數為k-1,則去掉此端點,再兩兩聯結此端點在G-e中……