k-連通圖中的可收縮團(tuán).pdf

1、k-連通圖G的一條邊或一個(gè)子圖是k-可收縮的，如果這條邊或這個(gè)子圖收縮后所得的圖仍是k-連通的。圖的團(tuán)是指圖中極大的完全子圖。Tutte證明了下面著名的結(jié)果：任意頂點(diǎn)數(shù)大于或等于5的3-連通圖都含有一條3-可收縮邊。C.Thomassen證明了任意不含三角形的k-連通圖都有一條k-可收縮的邊。這里的三角形是指長(zhǎng)為3的圈。Kawarabayashi證明了對(duì)于某個(gè)整數(shù)k≥4，任意的k-連通圖或者含有共享一條邊的兩個(gè)三角形，或者含有一條k-可

2、收縮的但不包含在任何三角形中的邊，或者含有一個(gè)k-可收縮的但不與其它三角形共享一條邊的三角形。顯然，Kawarabayashi的結(jié)果包含了C.Thomassen的結(jié)論。Tutte、Kawarabayashi和Thomassen等人的研究只是側(cè)重于k-連通圖中頂點(diǎn)數(shù)比較少的可收縮子圖的存在性，如邊或者三角形。另外一些研究者則對(duì)連通度作了限制，一般研究3-連通圖、4-連通圖、5-連通圖、6-連通圖。還有一些學(xué)者則是側(cè)重于一類對(duì)了圖有限制的連

3、通圖的可收縮邊的研究。在這篇論文里，我們研究了k-連通圖中子圖的頂點(diǎn)數(shù)比較多時(shí)k-可收縮子圖的存在性。結(jié)果表明這種可收縮子圖的存在性依賴于共享一條邊的三角形的數(shù)目。我們推廣了Kawarabayashi的技巧，并證明了一個(gè)更一般的有關(guān)k-可收縮團(tuán)的結(jié)論。 我們證明了對(duì)于t≥0和k≥max{4，t+3}，任意k-連通圖G或者包含有一個(gè)頂點(diǎn)數(shù)最多為t+2的可收縮團(tuán)，或者有一條邊包含在G的t+1個(gè)三角形中，或者存在G中的兩個(gè)團(tuán)至少共享一

4、條邊，或者圖G中有一個(gè)頂點(diǎn)數(shù)大于或等于4和一個(gè)頂點(diǎn)數(shù)大于或等于3的團(tuán)，它們的交是非空的。 本論文分為以下四個(gè)部分：在第一章里，我們給出了本文所用到的一些相關(guān)的圖論定義，并且回順了k-連通圖中k-可收縮子圖這個(gè)問題的背景和已有的結(jié)果；在第二章里，我們給出了本文的主要定理，并且指出該定理是Tutte、Kawarabayashi和C.Thomassen等人所做結(jié)果的推廣；在第三章里，我們給出了證明主要定理所需的四個(gè)引理以及它們的證明；