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

1、令G=(V,E)是一個連通圖.定義[A,B]為一端點在A中，另一端點在B中的邊的集合.G的邊割是指形為[U,(U)]的E(G)的子集，其中U是V(G)的非空子集，(U)=V(G)-U.設(shè)S(∈)E是G的一個邊割，如果G-S的每個連通分支至少有k個頂點，那么稱S是G的一個k-限制邊割.若G存在k-限制邊割，則稱G為λk-連通圖.稱G的所有k-限制邊割中所含邊數(shù)最少的邊割為G的λk-割，λk-割所含的邊數(shù)稱為G的k-限制邊連通度，記為λk(

2、G).令ξk(G)=min｛|[X,(X)]|:|X|=k，G[X]是連通的｝.若λk(G)=ξk(G)，則稱G是λk-最優(yōu)的.2004年，Volkmann等提出了在鄰域交條件下，圖是λ'-最優(yōu)的.本文把這些結(jié)果推廣到λk(G)-最優(yōu)的情況.文章主要討論了圖在鄰域交條件下的高階限制邊連通的最優(yōu)性問題.
　　本文分為四章.第一章是預(yù)備知識，介紹了一些本文中將要用到的圖論方面的基本概念和術(shù)語.
　　第二章簡要介紹了限制邊連通度的

3、發(fā)展現(xiàn)狀.
　　第三章給出了圖G是λk-連通的鄰域交條件.進一步，在某些條件下G是λk-最優(yōu)的.主要結(jié)果如下:
　　(1)設(shè)k是一個正整數(shù)且G是一個階不小于2k的圖.若對于G中任意不相鄰的頂點u，v都滿足|N(u)∩ N(v)|≥k，則G是λk-連通的且λk(G)≤ξk(G).
　　(2)設(shè)k是一個不小于3的正整數(shù)且G是一個階不小于2k的圖.若對于G中任意不相鄰的頂點u，v都滿足|N（u）∩N(v)|≥k且ξk(G)≤

4、(「)v/2」+k，則排除一類特殊圖外（見第三章），G是λk-最優(yōu)的.
　　(3)設(shè)k是一個不小于4的正整數(shù)且G是一個階不小于2k的圖.若對于G中任意不相鄰的頂點u，v都滿足|N(u)∩N(v)|≥k且ξk(G)≤(「)v/2」+k，則G是λk-最優(yōu)的.
　　第四章給出了連通圖G是λk-最優(yōu)的充分性條件.主要結(jié)果如下:
　　(1)設(shè)k是一個不小于2的正整數(shù)且G是一個階不小于2k的λk-連通圖.設(shè)S=[X，Y]是G的一個

5、滿足|X|≥k+1與|Y|≥k+1的λk-割.如果對于G中任意不相鄰的頂點u，v，當(dāng)u，v都不在三角形中時滿足|N(u)∩N(v)|≥k+1;當(dāng)u和v中至少有一個在三角形中時滿足|N(u)∩N(v)|≥2k-1，那么G[X]和G[Y]中分別存在一條k-路.
　　(2)設(shè)k是一個不小于2的正整數(shù)且G是一個階不小于2k的圖.如果對于G中任意不相鄰的頂點u，v，當(dāng)u，v都不在三角形中時滿足|N(u)∩N(v)|≥k+1;當(dāng)u，v至少有一