折疊交叉超立方體的2-額外連通度和2-額外邊連通度

郭慧媚, 阿依古麗·馬木提

(新疆大學 數學與系統科學學院, 新疆 烏魯木齊 830046)

現今,人們構建了各種各樣的互聯網絡.通過互聯網絡交換信息的具有高性能的多處理器系統需隨著實際生活的需要而被開發.一般來說,一個互聯網絡可以被視為一個無向圖G=(V,E),V中的每一個頂點就代表一個處理器,E中的每一條邊代表通信線路.連通度κ和邊連通度λ通常是用來衡量網絡可靠性和容錯性的參數[1-2].然而,這兩個參數只適用于一些互聯網絡.實際運用中的互聯網絡往往比較復雜,這兩種測量的參數都有一些缺陷,因為與某一個出錯的處理器鄰接的所有處理器或與某一個出錯的處理器關聯的所有通信線路并不總是同時失去運行能力.為了克服這一缺陷并獲得更準確的測量,推廣經典的連通度的概念很有必要.Harary 是第一個對連接組件增加限制的人,他定義了條件連通度[3].

n-維的超立方體Qn是經典的互聯網絡.這個網絡的許多性質已經被證明.當n≥3時,κ1(Qn)=2n-2;當n≥5時,κ2(Qn)=3n-5[5].當n≥3時,λ1(Qn)=2n-2;當n≥4時,λ2(Qn)=3n-4[6].折疊超立方體FQn是Qn的變體,首先由El-Amawy等[7]提出.文獻[6,8]證明了當n≥4時,κ1(FQn)=2n；當n≥8時,κ2(FQn)=3n-2；當n≥5 時,λ2(FQn)=3n-1.Xu等[9]證明了當n≥2時,λ1(FQn)=2n.在1992 年,Kemal[10]定義了n-維交叉超立方體.Chen等[11]證明了當n≥4時,κ1(CQn)=λ1(CQn)=2n-2.Yang等[12]證明了當n≥4時,λ2(CQn)=3n-4;當n≥5時,κ2(CQn)=3n-5.在CQn和FQn的基礎上,Zhang[13]在2002年定義了折疊交叉超立方體FCQn.比起前面的幾種互聯網絡,折疊交叉超立方體具有更多良好的性質,比如：更短的直徑、更短的平均節間距離,以及非常低的信息流量密度[14].最近,Cai等[15]證明了當n≥4時,κ1(FCQn)=λ1(FCQn)=2n.

本文主要證明了當n≥8時,κ2(FCQn)=3n-2;當n≥5時,λ2(FCQn)=3n-1.為了方便證明,在n+1維上討論.

1 預備知識

本節介紹一些定義、引理以及標號.

其中V(S)表示S中的頂點集,E(S) 表示S中的邊集.圖G的圍長g(G)表示G中的最短圈.本文中所用到的標號和定義可以參考文獻[1].

定義 1.1[16]兩個二進制字符串u=u1u0和v=v1v0被稱作是配對相關的,當且僅當它們滿足

(u,v)∈{(00,00),(01,11),(11,01),(10,10)},

用符號u～v表示；若u和v不配對相關,表示為uv.

n-維交叉超立方體CQn有2n個頂點和n2n-1條邊.關于CQn的定義如下.

1) 若n是偶數,則un-2=vn-2;

CQn中的任意2個點u=un-1un-2…u0,v=vn-1vn-2…v0是鄰接的當且僅當存在一個正整數l,1≤l≤n,使得下列4個條件同時被滿足:

1)iun-2…ul=ivn-2…vl;

2)ul-1≠vl-1;

3) 若l是偶數,ul-2=vl-2;

其中

因此,可以將FCQn表示為

其中

V(FCQ

E(FCQ

FCQ3和FCQ4如圖1所示.

圖 1 FCQ3與FCQ4

引理 1.4[16]κ(CQn)=λ(CQn)=n.

引理 1.5[11]當n≥3時,

κ1(CQn)=λ1(CQn)=2n-2.

引理 1.6[6,12]當n≥5時,κ2(CQn)= 3n-5;當n≥4時,λ2(CQn)= 3n-4.

引理 1.7[17]κ(FCQn)=λ(FCQn)=n+1.

引理 1.8[15]當n≥4時,CQn不含三圈.

引理 1.9[15]CQn中的任意2個點u和v最多有2個公共鄰點,即|NCQn(u)∩NCQn(v)|≤2.

引理 1.10[16]CQn中的任意2個點u和v含有2個公共鄰點當且僅當存在i、j滿足0≤i

證明已知uiui-1∈{00,01,10,11},當

綜上討論,引理成立.

引理 1.12[15]FCQn中的任意2個不同的點u和v最多含有2個公共鄰點,即

|NFCQn(u)∩NFCQn(v)|≤2.

引理 1.13[15]當n≥4時,FCQn中不含三圈.

引理 1.14FCQn中的任意一個點位于一個四圈中.

當i是偶數時,同樣可以找到一個點v滿足uj=vi,ui=vj,此時有

所以FCQn中的任意一個頂點u位于四圈uuivviu中,引理成立.

證明這個推論可以直接通過引理1.11以及對照表1～3得到,在這里不做過多贅述.

表 1 與u相關的點

表 2 與uiui-1相關的二進制字符串(I)

表 3 與uiui-1相關的二進制字符串(II)

2 主要結果

A={ui,(ui)n:i∈{0,1,2，…,n-1}}∩F,

B={(uj)t,((uj)t)n:t∈{0,1,2，…,n-1},t≠j}∩F,

C={(uk)i,((uk)i)n:i∈{0,1,2，…,n-1},i≠j,k},

|C∩F|≤|F-(A∪B∪D)|=
|F|-|A|-|B|-|D|≤n-3.

引理 2.2當n≥7時,κ2(FCQn+1)≤3n+1.

證明設C是FCQn+1中的四圈,P是這個四圈的二長路,顯然|NFCQn+1(P)|=3n+1.接下來,將證明NFCQn+1(P)使FCQn+1不連通,并且FCQn+1-(NFCQn+1(P)∪P)是含有至少3個頂點的連通分支.

并且

2n-6-(3n-5)-3>2n-22(n+1)>4,

|FCQn+1-(NFCQn+1(P)∪P)|≥3.

2n-(2n-1)-2-(n+2)-1>2n-22(n+1)>4,

通過上述分析,可以得到NFCQn+1(P)使FCQn+1不連通,FCQn+1去掉NFCQn+1(P)后剩下的每個連通分支都至少包含3個頂點,即

κ2(FCQn+1)≤3n+1.

引理 2.3當n≥7時,κ2(FCQn+1)≥3n+1.

|F′|=|F1|+1<2n-3+1=2n-2=κ1(CQn),

則0≤|Q|≤n-6,而且Q中的頂點可能位于

當|F1|=n-6+2+n時,可以得到

|F0|≤3n-|F1|=n+4,

且|H|=n+5.當|F1|=n-7+2+n時,可以得到

|F0|≤3n-|F1|=n+5,

因此,當|F|≤3n,且FCQn+1-F既不包含孤立點也不包含孤立邊時,FCQn+1-F是連通的.即當n≥7時,κ2(FCQn+1)≥3n+1.

定理 2.4當n≥7時,κ2(FCQn+1)=3n+1.

引理 2.6當n≥4時,λ2(FCQn+1)≤3n+2.

證明在FCQn+1中,設P是一條二長路,那么

引理 2.7當n≥4時,λ2(FCQn+1)≥3n+2.

|F1|<2n-2=λ1(CQn),

則

|B∩F|≤3n+1-n-n-3=n-2.

綜上所述,當|F|≤3n+1,FCQn+1-F既不包含孤立點,也不包含孤立邊時,可以得到FCQn+1-F是一個連通分支.即當n≥4時,λ2(FCQn+1)≥3n+2.

定理 2.8當n≥4時,λ2(FCQn+1)=3n+2.

3 結論

本文探究了n-維折疊交叉超立方體FCQn的2-額外連通度和2-額外邊連通度.FCQn是具有許多良好性質的網絡.證明當n≥8時,κ2(FCQn)=3n-2；當n≥5時,λ2(FCQn)=3n-1.也就是說,當n≥8時,至少要去掉3n-2個頂點,當n≥5時,至少要去掉3n-1條邊,使得FCQn不連通,并且剩下的每個連通分支至少有3個頂點.