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

1、設(shè)G是無向簡單連通圖，A和B是G的兩個(gè)不相交的頂點(diǎn)子集，定義[A，B]為一個(gè)端點(diǎn)在A中，另一個(gè)端點(diǎn)在B中的邊所成的集合.S=[X，Y]稱為G的邊割，其中X(∈)V(G)，Y=V(G)\X.設(shè)k是正整數(shù)，若G-S的每個(gè)連通分支都至少有k個(gè)點(diǎn)，則稱S是G的一個(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的每個(gè)最小k-限制邊割都能分離一個(gè)k階連通子圖，則稱G是超級(jí)-λk的.本文主要研究圖的k-限制邊連通性的最優(yōu)化問題，共分為四章.
　　第一章主要介紹一些本文將要用到的圖論方面的基本概念.
　　第二章給出圖是λ5-最優(yōu)和超級(jí)的鄰域交條件.主要結(jié)果如下:
　　(1)設(shè)G是階至少為21的λ5-連通圖.若對(duì)G中任意一對(duì)

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

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

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