連通圖中可去邊和圈的研究.pdf

1、圖論是離散數(shù)學(xué)中一個(gè)重要研究領(lǐng)域.它在計(jì)算機(jī)科學(xué),化學(xué),社會(huì)科學(xué)和生物學(xué)等方面都有很廣泛的應(yīng)用.
　　 連通圖的構(gòu)造是圖論中一個(gè)非常重要的研究課題.它與網(wǎng)絡(luò)模型和組合優(yōu)化聯(lián)系密切,使它具有重要的理論價(jià)值和應(yīng)用價(jià)值.自1961年,Tutte利用3連通圖中可收縮邊的存在性給出了3連通圖的構(gòu)造方法之后,人們致力于研究各種類型連通圖的構(gòu)造.可收縮邊和可去邊這兩個(gè)概念不僅在連通圖的構(gòu)造上發(fā)揮重要作用,而且還是遞歸證明圖的某些性質(zhì)的重要工具

2、.本文第二章至第四章主要研究連通圖中可收縮邊和可去邊的性質(zhì)以及他們在特定子圖上的分布情況.
　　 第二章主要研究了不含三角形的k連通圖中收縮邊的一個(gè)性質(zhì).設(shè) G是k連通圖,e=uv是圖 G中的一條邊.用G/e表示從圖 G中刪除頂點(diǎn) u,v,并添加新的頂點(diǎn) ve使得 ve與 u,v所有的鄰點(diǎn)相鄰所得到的圖.如果G/e仍然是k連通圖,那么 e=uv稱為圖 G的k可收縮邊.不存在k可收縮邊的非完全k連通圖稱為收縮臨界k連通圖.對于k=

3、3,Tutte[83]證明了階大于4的3連通圖存在3可收縮邊,所以不存在階大于4的收縮臨界3連通圖.對于 k=4,Martinov和 Fontet分別證明了收縮臨界4連通圖 G是4正則的,且每條邊恰在一個(gè)三角形上,即 G或者是 Cn2或者是7/2-邊連通立方體的線圖[32][59].這里7/2-邊連通立方體可由 K4或 K4,4中去掉1因子的圖通過構(gòu)造的方法得到.當(dāng)5≥5時(shí),收縮臨界 k連通圖的結(jié)構(gòu)比 k=3和 k=4的情況復(fù)雜得多.所

4、以對于k≥5的情形,人們一般考慮收縮臨界七連通圖的局部結(jié)構(gòu).1982年,Thomassen[81]證明了收縮臨界k連通圖含有三角形,即如果k連通圖G不含三角形,那么 G中存在一條邊 e=uv使得任何k點(diǎn)割都不同時(shí)包含頂點(diǎn)u和v.最近,Fujita等[37]證明了如果k連通圖G的最小度至少是[3k/2]+2,那么G有一條k可收縮邊 e=uv使得 G-{u,v}仍然是k連通的.結(jié)合以上兩個(gè)結(jié)果,我們證明以下結(jié)論,同時(shí)給出圖例說明最小度條件是

5、必須的.
　　 結(jié)論1設(shè)G是不含三角形的k連通圖,k≥2,如果δ(G)≥k+1,那么G中有一條邊e使得 G-V(e)仍是k連通的.
　　 對于k連通圖中的可去邊,Holton等[39]首先給出了3連通圖中可去邊的定義.后來尹建華在1999年定義了4連通圖可去邊的概念[93].最近廈門大學(xué)徐麗瓊在她的博士畢業(yè)論文[91]中把3連通圖和4連通圖的可去邊的概念推廣到k連通圖.設(shè)e是k連通圖G的一條邊,Gθ e表示圖G做下列運(yùn)算

6、所得的圖:(1)從G中去掉e得圖G-e；(2)如果e的某個(gè)端點(diǎn)在G-e中度數(shù)為k一1,則去掉此端點(diǎn),再兩兩連接此端點(diǎn)在G-e中的k-1個(gè)鄰點(diǎn)；(3)如果經(jīng)過(2)中的運(yùn)算后,有重邊出現(xiàn),則用單邊代替它們,使得此圖為簡單圖.如果 Gθ e仍為k連通圖,則稱e為G的可去邊.G的所有可去邊的集合記為En(G).早在1969年,類似于3連通圖中的可收縮邊的結(jié)果,Barnette等[12]證明了每個(gè)階大于4的3連通圖必有可去邊,并且給出了3連通圖

7、的一個(gè)遞歸構(gòu)造方法.這是關(guān)于可去邊的最早成果.尹建華[93]證明了4連通圖 G不存在可去邊的充要條件是 G是C52或 C62,并利用這個(gè)結(jié)果和4可收縮邊的性質(zhì)給出4連通圖的一個(gè)遞歸構(gòu)造方法,他的方法比Slater[71]的構(gòu)造方法簡單很多.徐麗瓊等[91][92]給出了k連通圖中可去邊的定義后,證明了不同構(gòu)于 K6的5連通圖中必有可去邊.另外對不含可去邊的k連通圖作了如下猜想:對于k(k≥3)連通圖G,G中不存在可去邊當(dāng)且僅當(dāng)k為奇數(shù)時(shí)

8、,G≌Kk+1；當(dāng)k為偶數(shù)時(shí),G≌Kk+1或H(k+2)/2,后來這個(gè)猜想被蘇健基等證實(shí)[76].至此k連通圖中的可去邊的存在性問題得到圓滿解決.同時(shí)可去邊在特殊子圖結(jié)構(gòu)上的分布問題也被廣泛研究,本文關(guān)于可去邊的結(jié)果就集中于此.
　　 第三章主要研究了3連通圖中可去邊的分布.蘇健基[72]證明了3連通圖的哈密頓圈上的可去邊數(shù)依賴于圖中極大半輪的個(gè)數(shù).我們把這個(gè)結(jié)果推廣到3連通圖的最長圈上.吳吉昌等[43][88]證明3連通3正則

9、圖的支撐樹上或者支撐樹外至少有2條可去邊.我們把這個(gè)結(jié)果推廣到不含極大半輪的3連通圖中.同時(shí)我們利用3連通圖可去邊的性質(zhì)證明了Thomassen在1976年提出的猜想(3連通圖的最長圈上有弦.)對兩類圖是成立的,并給出圖例說明這個(gè)結(jié)論沒有被之前的結(jié)果覆蓋.該章的結(jié)果列舉如下:
　　 結(jié)論2設(shè)G是階大于5的3連通圖并且G不是輪,C是G的最長圈,則(1)如果C不通過任何極大半輪,那么C上至少有3條可去邊；
　　 (2)如果

10、C僅通過一個(gè)極大半輪,那么C上至少有2條可去邊；
　　 (3)如果C僅通過兩個(gè)極大半輪,那么C上至少有1條可去邊.
　　 結(jié)論3設(shè)G是沒有極大半輪的3連通圖,那么G的支撐樹上或支撐樹外至少有2條可去邊.
　　 結(jié)論4設(shè)G是3連通圖且｜G｜≥6,C是圖G上的最長圈,如果｜E(C)∩ER(G)｜≤5,則 C上有弦.
　　 結(jié)論5設(shè) G是3連通圖且｜G｜≥9,C是圖G的最長圈,如果｜(E(G)-E(C))∩ER

11、(G)｜≤7而且G中任意的原子都跟C有交點(diǎn),則C上有弦.
　　 第四章主要研究了5連通圖中可去邊的分布.徐麗瓊在給出5連通圖的可去邊的定義后討論了它的分布情況,并證明了[91]對于5連通圖G,如果最小度至少是6或圍長至少是4或G中不含原子,那么G中任意的圈C至少有兩條可去邊；如果最小度至少是6或圍長至少是4,那么G中任意的支撐樹T上至少有兩條可去邊.我們推廣了上述結(jié)果.
　　 結(jié)論6設(shè)G是階大于7的5連通圖,那么G上任意

12、的三角形上有1條可去邊.
　　 結(jié)論7設(shè)G是階大于9的5連通圖,C是G的一個(gè)圈,那么(1)如果C與任何原子都是點(diǎn)不交的,則C上有2條可去邊；
　　 (2)如果C僅與一個(gè)原子有交點(diǎn),則C上有1條可去邊；
　　 (3)如果G中不含原子且C是哈密頓圈,則C至少有3條可去邊；
　　 (4)如果G中每對相鄰的點(diǎn)對x,y都有d(x)+d(y)≥11成立,則C上有2條可去邊.
　　 結(jié)論8設(shè)G是階大于9的5連通

13、圖,T是G的支撐樹,如果G不含原子,則T上有2條可去邊.
　　 論文的最后一部分是關(guān)于圖的棱可圈性.圖G的棱是指G與完全圖K2的笛卡爾積,記作 G□K2.如果 G□K2是哈密頓的,那么稱圖G是棱哈密頓的.對于圖G的非空頂點(diǎn)子集 S,若G中存在一個(gè)圈經(jīng)過S的所有頂點(diǎn),那么稱S是可圈的；若 G□K2中存在一個(gè)圈經(jīng)過S以及它的拷貝S'中所有的頂點(diǎn),那么稱 S是棱可圈的.圖的哈密頓圈問題是圖論中的一個(gè)經(jīng)典問題.自1857年Hamilto

14、n正式引入這個(gè)概念以來已有大量的定理、猜想、綜述.最近一個(gè)研究趨勢是尋找哈密頓圈的變形來衡量圖距離哈密頓性“有多近”,圖的棱哈密頓性就是其中之一.最近,Ozeki[65]首次研究了圖具有棱哈密頓性的度和條件,證明了對階n≥2的連通圖G,如果σ3(G)≥n,那么G是棱哈密頓的.同時(shí)他們給出實(shí)例說明所得的界是最好的.我們把這個(gè)結(jié)果推廣到特定子集上,另外我們還討論了無爪圖的情形.
　　 結(jié)論9設(shè)G是連通圖且它的階n≥2,φ≠S V(G