圖的高階限制邊連通度.pdf

1、圖的邊連通度和超邊連通性常用來度量網(wǎng)絡(luò)的可靠性，但是當(dāng)兩個(gè)圖具有相同的邊連通度和超邊連通性時(shí)，就無法對(duì)其可靠性進(jìn)行比較。因此，為了更精確地度量網(wǎng)絡(luò)可靠性，人們提出了m-限制邊連通度的概念：設(shè)m是正整數(shù)，連通圖G的邊割S稱為m-限制邊割，如果G-S的每個(gè)連通分支都至少包含m個(gè)頂點(diǎn)；G中最小m-限制邊割的基數(shù)稱為圖G的m-限制邊連通度，記為λm(G)。當(dāng)m=2時(shí)，λ2(G)稱為圖G的限制邊連通度，通常記為λ'(G)。如果λm(G)存在，則稱

2、G是λm-連通圖。目前，關(guān)于m-限制邊連通度方面的研究，主要集中在討論m-限制邊連通度的存在性及上界，計(jì)算特殊圖類或網(wǎng)絡(luò)的m-限制邊連通度，尋求分別具有極大m-限制邊連通度和較少最小m-限制邊割數(shù)的圖類等方面。令ζm(G)：=min{｜[X，X]｜：X V(G)，｜X｜=m，且G[X]連通。如果圖G的m-限制邊割S=[X，X]，滿足｜X｜=m或｜X｜=m，則稱S是平凡的。設(shè)λm-連通圖G滿足λm(G)≤ζm(G)，如果λm(G)=ζm(

3、G)，則稱G是最優(yōu)m-限制邊連通圖，簡(jiǎn)稱入m-最優(yōu)圖；如果G的每個(gè)最小m-限制邊割都是平凡的，則稱G是超級(jí)m-限制邊連通圖，簡(jiǎn)稱超-λm連通圖。一般來說，λm-最優(yōu)圖和超λm連通圖具有較高的可靠性。 本文共分五章，第一章綜述m-限制邊連通度的應(yīng)用背景及研究進(jìn)展，介紹本文用到的一些基本概念，術(shù)語(yǔ)和記號(hào)，并概述本文的研究?jī)?nèi)容及獲得的主要結(jié)果。 第二章主要研究滿足λm(G)≤ζm(G)的一個(gè)一般充分條件。已經(jīng)證明，當(dāng)m≤3時(shí)，

4、λm-連通圖G具有λm(G)≤ζm(G)這一性質(zhì)。當(dāng)m≥4時(shí)，Bonsma等人指出不等式λm(G)≤ζm(G)一般不再成立。歐見平于2007年證明階大于等于11的λ4-連通圖G滿足λ4(G)≤ζ4(G)。本章我們通過研究滿足λm(G)>ζm(G)的λm-連通圖所具有的結(jié)構(gòu)性質(zhì)，不僅易得歐見平的以上結(jié)論，而且還得到了如下結(jié)論：當(dāng)m≥5時(shí)，階大于m(m-1)的λm-連通圖G均滿足λm(G)≤ζm(G)。最后，通過構(gòu)造例子來說明我們給出的條件

5、是最好的。 第三章主要研究圖的最優(yōu)限制邊連通性。給出并證明一般圖，二部圖，以及直徑為2的圖分別是λ'-最優(yōu)圖的充分條件，同時(shí)通過構(gòu)造例子來說明這些條件不能被減弱。本章得到的結(jié)論是對(duì)Hellwig與Volkmann 2004和2005年相應(yīng)結(jié)論的改進(jìn)，其中關(guān)于直徑為2圖的λ'-最優(yōu)性結(jié)論是對(duì)王應(yīng)前和李喬1999年結(jié)論的進(jìn)一步推廣。 第四章主要研究圖的超級(jí)限制邊連通性。給出并證明一般圖，二部圖，無三角形圖，以及直徑為2的圖分

6、別是超-λ'連通圖的充分條件，并用例子說明這些條件是最好的。本章所得的結(jié)論推廣了王應(yīng)前和李喬2001年的結(jié)論。而關(guān)于直徑為2圖的超-λ' 連通性，在不含三角形的條件下，我們得到的推論與王世英和林上為2007年的結(jié)論類似，并且推廣了范英梅2003年的結(jié)論. 第五章主要研究圖的λ3-最優(yōu)性和超-λ3連通性.首先討論λ3-最優(yōu)與λ'-最優(yōu)和超-λ'連通之間的關(guān)系.然后給出并證明一般圖,二部圖,無三角形圖，以及直徑為2的圖分別是