圖的k階限制邊連通性.pdf

1、設G是無向簡單連通圖，A和B是G的兩個不相交的頂點子集，定義[A，B]為一個端點在A中，另一個端點在B中的邊所成的集合.S=[X，Y]稱為G的邊割，其中X(∈)V(G)，Y=V(G)\X.設k是正整數(shù)，若G-S的每個連通分支都至少有k個點，則稱S是G的一個k-限制邊割.若G存在k-限制邊割，則稱G為λk-連通圖.G的最小k-限制邊割所含的邊數(shù)稱為G的k-限制邊連通度，記為λk(G).令ξk(G)=min{|[X，(X)|:X(∈)V(G

2、)，|X|=k，G[X]連通}，其中(X)=V(G)\X.若λk(G)=ξk(G)，則稱G是λk-最優(yōu)的.若G的每個最小k-限制邊割都能分離一個k階連通子圖，則稱G是超級-λk的.本文主要研究圖的k-限制邊連通性的最優(yōu)化問題，共分為四章.
　　第一章主要介紹一些本文將要用到的圖論方面的基本概念.
　　第二章給出圖是λ5-最優(yōu)和超級的鄰域交條件.主要結果如下:
　　(1)設G是階至少為21的λ5-連通圖.若對G中任意一對

3、不相鄰的頂點u和v都有|N(u)∩ N(v)|≥5，且ξ5(G)≤(「)v/2」+10，則除一類特殊圖外，G是λ5-最優(yōu)的.
　　(2)設G是階至少為21的λ5-連通圖.若對G中任意一對不相鄰的頂點u和v都有|N(u)∩ N(v)|≥6，且ξ5(G)≤(「)v/2」+11，則G是超級-λ5的.
　　第三章給出圖是λ5-最優(yōu)和超級的度條件.主要結果如下:
　　(1)設G是階至少為21的λ5-連通圖.對G中任意一對頂點x和

4、y，當d(x，y)=2時，d（x）+d（y）≥2(「)v/2」+3;當d(x，y)=3時，d(x)+d（y）≥2(「)v/2」-1;當d（x，y）=4時，d（x）+d（y）≥2(「)v/2」-5;當d（x，y）=5時，d(x)+d（y）≥2(「)v/2」-9，且在G的任意一個同構于K6的子圖中都存在一個點v滿足d(v)≥(「)v/12」+4，則G是λ5-最優(yōu)的.
　　(2)設G是階至少為21的λ5-連通圖.對G中任意一對頂點x和y

5、，當d(x，y)=2時，d（x）+d（y）≥2(「)v/2」+5;當d(x，y)=3時，d(x)+d（y）≥2(「)v/2+1;當d（x，y）=4時，d(x)+d（y）≥2(「)v/2」-3;當d(x，y)=5時，d(x)+d（y）≥2(「)v/2」-7，且在G的任意一個同構于K6的子圖中都存在一個點v滿足d(v)≥(「)v/2」+5，則G是超級-λ5的.
　　第四章主要研究圖的λk-最優(yōu)性和超級性之間的關系.結果如下: