五邑大学学报：自然科学版
五邑大學學報：自然科學版
오읍대학학보：자연과학판
Journal of Wuyi University(Natural Science Edition)
2012年
3期
6-11
,共6页
广义DeBruijn图%边割%限制边连通度
廣義DeBruijn圖%邊割%限製邊連通度
엄의DeBruijn도%변할%한제변련통도
generalized De Bruijn graphs%edge cut%restricted edge connectivity
m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.
m-限製邊割將連通圖G分離成階不小于m的連通分支,圖G的最小m-限製邊割所含的邊數稱為圖G的m-限製邊通度,記作λm（G）.對于包含m-限製邊割的連通圖G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,則稱圖G是極大m-限製邊連通的.本文證明：噹n≥7時,無嚮廣義De Bruijn圖UBG（2,n）是極大m-限製邊連通的（m={2,3}）.
m-한제변할장련통도G분리성계불소우m적련통분지,도G적최소m-한제변할소함적변수칭위도G적m-한제변통도,기작λm（G）.대우포함m-한제변할적련통도G,유λm（G）≤ξm（G）（m≤3）;여과λm（G）=ξm（G）,칙칭도G시겁대m-한제변련통적.본문증명：당n≥7시,무향엄의De Bruijn도UBG（2,n）시겁대m-한제변련통적（m={2,3}）.
An m-restricted edge cut is an edge cut of a connected graph that disconnects this graph into each components having order at least m.The minimum size m-restricted edge cut of graph G is m-restricted edge connectivity,denoted by λm（G）.It is known that λm（G） ≤ ξm（G） holds for graph G that contain m-restricted edge cut whenever m ≤ 3.Graph G is maximally m- restricted edge connected if λm（G）=ξ m（G）.In this paper,for some m = { 2,3},undirected generalized De Bruijn graphs UBG（2,n） are proved to be maximally m-restricted edge connected whenever n ≥ 7.
