關(guān)于圖的k階限制邊連通度一些問題的研究.pdf

1、圖的限制連通性問題一直是圖論的一個(gè)核心課題.由于限制連通度能度量網(wǎng)絡(luò)的可靠性和容錯(cuò)性，伴隨著互連網(wǎng)絡(luò)的快速發(fā)展，近年來對(duì)圖的限制連通性進(jìn)行了廣泛研究.設(shè)G=(V, E)是有限簡(jiǎn)單無向圖，其中V=V(G)和E=E(G)分別是G的頂點(diǎn)集和邊集.設(shè)S是連通圖G的一個(gè)邊割，若G-S的每個(gè)連通分支都至少有k個(gè)點(diǎn)，則稱S是G的一個(gè)k-限制邊割.稱G中所含邊數(shù)最少的k-限制邊割為λk-割.記G的k-限制邊連通度λk=λk(G)為λk-割所含的邊數(shù).定

2、義ξk(G)=min{|[X，(X)]|:X(C)V(G)，|X|=k，G[X]是連通子圖}，若λk(G)=ξk(G)，則稱G是λk-最優(yōu)圖.
　　在本文中，我們主要研究幾類圖限制邊連通度的一些問題.本文共分三章:
　　第一章，介紹了文章所涉及的一些概念、術(shù)語和符號(hào).
　　第二章，給出了λ5-最優(yōu)圖的一個(gè)充分條件.主要結(jié)果如下:
　　設(shè)G是一個(gè)v≥17，δ≥([)v/2」-4且λ5(G)≤ξ5(G)的λ5-連通圖

3、，若
　　(i)G中每個(gè)導(dǎo)出六圈以及任意由一條邊相連的兩個(gè)三角形的粘合圖中都存在非粘合點(diǎn)u滿足d（u）≥([)v/2」-2;
　　(ii)G中每個(gè)導(dǎo)出五圈以及任意兩個(gè)三角形的粘合圖中都存在非粘合點(diǎn)v滿足d(v)≥([)v/2];
　　(iii)G中每個(gè)四圈上都存在一點(diǎn)w滿足d（w）≥([)v/2」+4，則G是λ5-最優(yōu)圖.
　　第三章，給出了λ4-最優(yōu)圖的一個(gè)度條件.主要結(jié)果如下:
　　設(shè)G是一個(gè)v≥11的