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

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

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 新疆 烏魯木齊 830046)

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

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

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

1 預(yù)備知識(shí)

本節(jié)介紹一些定義、引理以及標(biāo)號(hào).

其中V(S)表示S中的頂點(diǎn)集,E(S) 表示S中的邊集.圖G的圍長(zhǎng)g(G)表示G中的最短圈.本文中所用到的標(biāo)號(hào)和定義可以參考文獻(xiàn)[1].

定義 1.1[16]兩個(gè)二進(jìn)制字符串u=u1u0和v=v1v0被稱作是配對(duì)相關(guān)的,當(dāng)且僅當(dāng)它們滿足

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

用符號(hào)u～v表示；若u和v不配對(duì)相關(guān),表示為uv.

n-維交叉超立方體CQn有2n個(gè)頂點(diǎn)和n2n-1條邊.關(guān)于CQn的定義如下.

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

CQn中的任意2個(gè)點(diǎn)u=un-1un-2…u0,v=vn-1vn-2…v0是鄰接的當(dāng)且僅當(dāng)存在一個(gè)正整數(shù)l,1≤l≤n,使得下列4個(gè)條件同時(shí)被滿足:

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

2)ul-1≠vl-1;

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

其中

因此,可以將FCQn表示為

其中

V(FCQ

E(FCQ

FCQ3和FCQ4如圖1所示.

圖 1 FCQ3與FCQ4

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

引理 1.5[11]當(dāng)n≥3時(shí),

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

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

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

引理 1.8[15]當(dāng)n≥4時(shí),CQn不含三圈.

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

引理 1.10[16]CQn中的任意2個(gè)點(diǎn)u和v含有2個(gè)公共鄰點(diǎn)當(dāng)且僅當(dāng)存在i、j滿足0≤i

證明已知uiui-1∈{00,01,10,11},當(dāng)

綜上討論,引理成立.

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

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

引理 1.13[15]當(dāng)n≥4時(shí),FCQn中不含三圈.

引理 1.14FCQn中的任意一個(gè)點(diǎn)位于一個(gè)四圈中.

當(dāng)i是偶數(shù)時(shí),同樣可以找到一個(gè)點(diǎn)v滿足uj=vi,ui=vj,此時(shí)有

所以FCQn中的任意一個(gè)頂點(diǎn)u位于四圈uuivviu中,引理成立.

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

表 1 與u相關(guān)的點(diǎn)

表 2 與uiui-1相關(guān)的二進(jìn)制字符串(I)

表 3 與uiui-1相關(guān)的二進(jìn)制字符串(II)

2 主要結(jié)果

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當(dāng)n≥7時(shí),κ2(FCQn+1)≤3n+1.

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

并且

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)后剩下的每個(gè)連通分支都至少包含3個(gè)頂點(diǎn),即

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

引理 2.3當(dāng)n≥7時(shí),κ2(FCQn+1)≥3n+1.

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

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

當(dāng)|F1|=n-6+2+n時(shí),可以得到

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

且|H|=n+5.當(dāng)|F1|=n-7+2+n時(shí),可以得到

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

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

定理 2.4當(dāng)n≥7時(shí),κ2(FCQn+1)=3n+1.

引理 2.6當(dāng)n≥4時(shí),λ2(FCQn+1)≤3n+2.

證明在FCQn+1中,設(shè)P是一條二長(zhǎng)路,那么

引理 2.7當(dāng)n≥4時(shí),λ2(FCQn+1)≥3n+2.

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

則

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

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

定理 2.8當(dāng)n≥4時(shí),λ2(FCQn+1)=3n+2.

3 結(jié)論

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