2-Hamming 圖的強(qiáng)Menger 邊連通容錯(cuò)性?

解國(guó)強(qiáng)，孟吉翔

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

0 引言

并行路由(即頂點(diǎn)不相交路徑的構(gòu)造) 一直是互聯(lián)網(wǎng)絡(luò)中的一個(gè)重要問(wèn)題. 通過(guò)頂點(diǎn)間的不相交的路徑不僅可以避免通信瓶頸, 提高信息傳輸?shù)男? 而且在頂點(diǎn)故障的情況下提供了替代路徑. 隨著互聯(lián)網(wǎng)絡(luò)規(guī)模的不斷增加, 路由發(fā)生故障不可避免, 這與相應(yīng)圖的連通性密切相關(guān).

為了更好地反映出網(wǎng)絡(luò)的頂點(diǎn)不交路的容錯(cuò)性, Oh 等[1]提出了強(qiáng)Menger 連通性的概念, 并證明了n維星圖(n-dimensional star graphs)在n≥3 時(shí)是(n-3)-容錯(cuò)強(qiáng)Menger 連通的. Shih 等[2]證明了所有n維超立方體網(wǎng)絡(luò)(n-dimensional hypercubes)在n≥2 時(shí)是(n-2)-容錯(cuò)強(qiáng)Menger 連通的,并且在n≥5 時(shí)是(2n-5)-條件容錯(cuò)強(qiáng)Menger 連通的. Chen 等[3]證明了n維增廣立方體(n-dimensional augmented cubes)在n≥4 時(shí)是(2n-7)-容錯(cuò)強(qiáng)Menger 連通的. Cai 等[4]證明了n維冒泡星圖(n-dimensional bubble-sort star graphs)在n≥4 時(shí)是(2n-5)-容錯(cuò)強(qiáng)Menger 連通的. Yang 等[5]證明了折疊超立方體(folded hypercubes)在n≥6 時(shí)是(n-1)-容錯(cuò)強(qiáng)Menger 連通的, 并且在n≥8 時(shí)是(2n-3)-條件容錯(cuò)強(qiáng)Menger 連通的. Li 等[6]證明了n維平衡超立方體(n-dimensional balanced hypercubes)在n≥2 時(shí)是(2n-4)-條件容錯(cuò)強(qiáng)Menger 連通的.

為了更好地反映出網(wǎng)絡(luò)的邊不交路的容錯(cuò)性, Qiao 等[7]提出了強(qiáng)Menger 邊連通性的概念,并證明了n維超立方體在n≥4 時(shí)是(2n-4)-條件邊容錯(cuò)強(qiáng)Menger 邊連通的, 而n維折疊超立方體在n≥5 時(shí)是(2n-2)-條件邊容錯(cuò)強(qiáng)Menger 邊連通的. Cheng 等[8]改進(jìn)了這個(gè)結(jié)論, 證明了n維折疊超立方體在n≥5 時(shí)是(3n-5)-條件邊容錯(cuò)強(qiáng)Menger 邊連通的. Li 等[6]證明了n維平衡超立方體在n≥2 時(shí)是(2n-2)-邊容錯(cuò)強(qiáng)Menger 邊連通的,并且在n≥2 時(shí)是(6n-8)-條件邊容錯(cuò)強(qiáng)Menger 邊連通的.

本文將介紹一類新的網(wǎng)絡(luò)結(jié)構(gòu),稱為h-Hamming 圖.h-Hamming 圖是一般的Hamming 圖的推廣,而且k-元n-立方體, Harary 圖也被包含在這個(gè)網(wǎng)絡(luò)當(dāng)中.h-Hamming 圖是Caylay 圖, 具有簡(jiǎn)單而豐富的拓?fù)湫再|(zhì). 本文主要探討2-Hamming 圖的強(qiáng)Menger 邊連通容錯(cuò)性, 得到2-Hamming 圖H(n,k,2)(n≥2,k≥5)是(4n-2)-邊容錯(cuò)強(qiáng)Menger 邊連通的, 但不是(4n-1)-邊容錯(cuò)強(qiáng)Menger 邊連通的.

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

設(shè)G=(V(G),E(G))是一個(gè)頂點(diǎn)集為V(G)和邊集為E(G)的有限圖, 用|V(G)|和|E(G)|表示圖G的點(diǎn)數(shù)和邊數(shù). 對(duì)于一個(gè)頂點(diǎn)子集U?V(G),由頂點(diǎn)集U導(dǎo)出的子圖記為G[U]. 圖G中的一個(gè)頂點(diǎn)u的鄰集用NG(u)表示, 或簡(jiǎn)寫為N(u).N(u)中的頂點(diǎn)個(gè)數(shù)稱為u的度, 記作dG(u). 圖G的最小度用δ(G)表示. 對(duì)于一個(gè)子圖H?G,u∈V(H), 定義dH(u)=|NH(u)|. 設(shè)x,y∈V(G), 一個(gè)(x,y)-邊割是E的一個(gè)邊子集S, 其中x和y分別屬于G-S的兩個(gè)不同的分支. 令A(yù),B是G的子圖,E(A,B)表示一個(gè)端點(diǎn)在A中, 另一個(gè)端點(diǎn)在B中的邊構(gòu)成的集合. 圖G的最大分支的頂點(diǎn)數(shù)記作mc(G). 本文中沒有定義的術(shù)語(yǔ)和符號(hào), 請(qǐng)參閱文獻(xiàn)[9].

定理1[10]設(shè)x和y為圖G的兩個(gè)相異頂點(diǎn),x和y之間邊不交的路的條數(shù)的最大值等于(x,y)-邊割的最小基數(shù).

定義1[7]設(shè)G為一個(gè)連通圖, 若G中的每一對(duì)頂點(diǎn)x,y之間都有min{dG(x),dG(y)}條邊不交的路, 則G為強(qiáng)Menger 邊連通圖.

定義2[7]設(shè)G為強(qiáng)Menger 邊連通圖,m為非負(fù)整數(shù), 若對(duì)于任意的F?E(G)且|F|≤m,G-F仍是強(qiáng)Menger 邊連通的, 則G為m-邊容錯(cuò)強(qiáng)Menger 邊連通圖.

設(shè)Γ 是一個(gè)群,S是群Γ 的一個(gè)不包含單位元的生成子集,并且滿足S=S-1. Cayley 圖C(Γ,S)是頂點(diǎn)集為Γ 的圖,對(duì)于Γ 中的任意兩個(gè)不同的元x和y,x與y在C(Γ,S)中相鄰當(dāng)且僅當(dāng)x-1y∈S. 設(shè)Zk={0,1,···,k-1}是模k的剩余類加群,S?Zk{0},S=-S. Cayley 圖C(Zk,S)通常稱為循環(huán)圖.

h-Hamming 圖H(n,k,h), 1 ≤h≤k-1, 其頂點(diǎn)集為{(i1,i2,···,in)|ip∈Zk,1 ≤p≤n}, 其中(i1,i2,···,in)與(j1,j2,···,jn) 相鄰當(dāng)且僅當(dāng)存在r(1 ≤r≤n), 使得當(dāng)p/=r時(shí), 有ip=jp, 且當(dāng)p=r時(shí), 有jp-ip∈{±1,±2,···,±h}(modk).為了方便,本文在類似的表述中省略了“(modk)”.H(1,5,2)和H(1,6,2)如圖1 所示.

設(shè)z∈Zk, 令Vz={u|u=a1a2···an-1z∈V(H(n,k,h))}. 由H(n,k,h)的頂點(diǎn)集Vz導(dǎo)出的子圖, 記為單元R[z]. 易知, 當(dāng)n≥2 時(shí),R[z]同構(gòu)于H(n-1,k,h).R[z]中的每一個(gè)頂點(diǎn)v, 其不在V(R[z])中的鄰點(diǎn)稱為v的外鄰點(diǎn). 顯然,v恰有4 個(gè)外鄰點(diǎn), 它們分別位于不同的單元R[z-2],R[z-1],R[z+1]和R[z+2]中.

2 邊容錯(cuò)強(qiáng)Menger 邊連通性

H(n,k,h)是交換群上的一個(gè)Cayley 圖, 因而是點(diǎn)傳遞的, 由此可知其邊連通度為其正則度[18], 于是我們得到引理1.

引理1λ(H(n,k,2))=δ(H(n,k,2))=4n, 其中n≥1,k≥5.

引理2[19]設(shè)S?E(H(1,k,2))(k≥5)且|S|≤5, 則在H(1,k,2)-S中存在一個(gè)分支Y, 使得|V(Y)|≥k-1,即mc(H(1,k,2)-S)≥k-1.

引理3設(shè)S?E(H(2,k,2))(k≥5)且|S|≤13, 則在H(2,k,2)-S中存在一個(gè)分支Y, 使得|V(Y)|≥k2-1,即mc(H(2,k,2)-S)≥k2-1.

證明記Sj=S∩E(R[j]), 設(shè)Yj為R[j]-Sj中的最大分支, 其中j=0,1,···,k-1. 記Mij=E(R[i],R[j]),Tij=S∩Mij, 并且T= ∪Tij, 其中0 ≤i≤k-1,j=i+1,i+2,i-1,i-2. 于是記H(n,k,2)-S中的一個(gè)最大分支為Y. 不失一般性, 設(shè)S0,S1,···,Sk-1中邊數(shù)最多的是S0, 邊數(shù)第二多的是Sr(r/=0), 邊數(shù)第三多的是St(t/=0,r). 易得,|Sr|≤?13/2」=6, |St|≤?13/3」=4.

情形1|S0|≤3.

由λ(R[i])=4 可知,R[i]-Si連通,其中i∈{0,1,···,k-1}. 進(jìn)一步有R[i]-Si=Yi,其中i∈{0,1,···,k-1}. 根據(jù)2-Hamming 圖的定義可知,R[i]與R[i+j](R[i-j])之間有完美匹配并且恰有k條邊, 其中i∈{0,1,···,k-1},j∈{1,2}. 因?yàn)?k≥15 > 13 ≥|T|, 所以是連通的. 因此H(2,k,2)-S是連通的, 并且|V(Y)|=k2≥k2-1.

情形24 ≤|S0|≤5.

情形2.1|Sr|≤3.

由λ(R[i])=4 可知,R[i]-Si連通, 并且R[i]-Si=Yi, 1 ≤i≤k-1. 因?yàn)镽[i]與R[i+j](R[i-j])之間有完美匹配并恰有k條邊, 其中i∈{1,2,···,k-1},j∈{1,2}, 又因?yàn)?k>9, 所以是連通的. 又由4k-4>9 可知,在H(2,k,2)中存在一條邊e,并且滿足一個(gè)端點(diǎn)在Y0中,另一個(gè)端點(diǎn)在Y1,Y2,Yk-2或Yk-1中. 所以連通.于是并且(k-1)k+(k-1)=k2-1.

情形2.24 ≤|Sr|≤5.

情形2.2.1|St|≤3.

由λ(R[i])=4 可知,R[i]-Si是連通的, 且R[i]-Si=Yi, 其中i/∈{0,r}. 根據(jù)2-Hamming 圖的定義,R[i]與R[i+j](R[i-j])之間有完美匹配并恰有k條邊, 其中i/∈{0,r},j∈{1,2}. 又因?yàn)?k>5 ≥|S|-|S0|-|Sr|≥|T|,所以是連通的. 由引理2 可知,|V(Y0)|≥k-1 和|V(Yr)|≥k-1, 下面考慮r的值.(1) 如果r∈{1,2,k-2,k-1}. 不妨設(shè)r=1. 由3k-3>5 ≥|T|可知, 在H(2,k,2)中, 存在一條邊e1, 使得一個(gè)端點(diǎn)在Y0中, 另一個(gè)端點(diǎn)在Y2,Yk-2或Yk-1中. 并且, 在H(2,k,2)中也存在一條邊e2, 使得一個(gè)端點(diǎn)在Y1中, 另一個(gè)端點(diǎn)在Y2,Y3或Yk-1中.

(2) 如果r/∈{1,2,k-2,k-1}, 因?yàn)?k-4>5 ≥|T|, 所以在H(2,k,2)中存在一條邊e1, 使得一個(gè)端點(diǎn)在Y0中, 另一個(gè)端點(diǎn)在Y1,Y2,Yk-2或Yk-1中. 并且在H(2,k,2)中也存在一條邊e2, 使得一個(gè)端點(diǎn)在Yr中, 另一個(gè)端點(diǎn)在Yr+1,Yr+2,Yr-2或Yr-1中.

因此, 在H(2,k,2)-S中,Y0與連通, 且Yr與連通. 于是,若|V(Y)|=k2-2, 則|S|≥|E(Y,H(2,k,2)-Y)|≥14, 這與|S|≤13 矛盾. 因此|V(Y)|≥k2-1.

情形2.2.2|St|=4.

因?yàn)閨S0|≥|Sr|≥|St|≥4 以及|S|≤13, 所以又由λ(R[i])=4 可知,R[i]-Si連通,且R[i]-Si=Yi,其中i/∈{0,r,t}. 由引理2 可知,|V(Y0)|≥k-1,|V(Yr)|≥k-1,|V(Yt)|≥k-1. 因?yàn)槭沁B通的, 又因?yàn)樵贖(2,k,2)中, 每個(gè)單元R[j]中的任意頂點(diǎn)都有4 個(gè)外鄰點(diǎn), 其中j=0,r,t, 所以H(2,k,2)-S是連通的. 故|V(Y)|=k2.

情形36 ≤|S0|≤9.

情形3.1|Sr|≤3.

因?yàn)棣?R[i])=4, 所以R[i]-Si是連通的, 并且R[i]-Si=Yi, 1 ≤i≤k-1. 根據(jù)2-Hamming 圖的定義,R[i]與R[i+j](R[i-j])之間有完美匹配并恰有k條邊, 其中i∈{1,2,···,k-1},j∈{1,2}. 又因?yàn)?k>7 ≥|T|, 所以是連通的. 若|V(Y)|≤kn-2, 則在圖H(n,k,2)-S中,R[0]-S0中至少有兩個(gè)頂點(diǎn)沒有外鄰點(diǎn), 于是, |T|≥8, 這與|T|≤|S|-|S0|≤7 矛盾. 因此, |V(Y)|≥k2-1.

情形3.24 ≤|Sr|≤5.

由引理2 可知, |V(Yr)|≥k-1. 因?yàn)樗訰[i]-Si是連通的且R[i]-Si=Yi, 其中i/∈{0,r}. 由于是連通的. 又因?yàn)樵贖(2,k,2)中,R[0]中的任意頂點(diǎn)都有4 個(gè)外鄰點(diǎn), 所以是連通的. 于是,|V(Y)|≥k2-1.

情形3.3|Sr|=6.

由λ(R[i])=4 可知,R[i]-Si是連通的, 且R[i]-Si=Yi,i/∈{0,r}. 因?yàn)閨T|≤|S|-|S0|-|Sr|≤1

情形410 ≤|S0|≤13.

引理4設(shè)S?E(H(n,k,2))(n≥2,k≥5) 且|S| ≤8n-3, 則在H(n,k,2)-S中存在一個(gè)分支Y, 使得|V(Y)|≥kn-1, 即mc(H(n,k,2)-S)≥kn-1.

證明用歸納法, 分別由引理2 和引理3 可知, 當(dāng)n=1,2 時(shí)結(jié)論成立. 假設(shè)該結(jié)論對(duì)于n-1 時(shí)成立(其中n≥3). 記H(n,k,2)-S中的一個(gè)最大分支為Y. 下面證明結(jié)論對(duì)于n時(shí)也成立. 記Sj=S∩E(R[j]), 設(shè)Yj為R[j]-Sj中的最大分支, 其中j=0,1,···,k-1. 記Mij=E(R[i],R[j]),Tij=S∩Mij, 并且T=∪Tij, 其中0 ≤i≤k-1,j=i+1,i+2,i-1,i-2. 于是不失一般性, 設(shè)S0,S1,···,Sk-1中邊數(shù)最多的是S0, 邊數(shù)第二多的是Sr(r/=0). 易得, |Sr|≤?(8n-3)/2」=4n-2.

情形1|S0|≤4n-5.

由λ(R[i])=4n-4 可知,R[i]-Si是連通的,且R[i]-Si=Yi,其中i∈{0,1,···,k-1}. 又因?yàn)閨Mj,j+1|-|Tj,j+1|≥kn-1-(8n-3)≥1, 所以|E(Yj,Yj+1)|≥1, 其中0 ≤j≤k-1,n≥3,k≥5. 故H(n,k,2)-S是連通的, |V(Y)|=kn≥kn-1.

情形24n-4 ≤|S0|≤8n-11=8(n-1)-3.

由歸納假設(shè)可知, |V(Y0)|≥kn-1-1.

情形2.1|Sr|≤4n-5.

由λ(R[i]) = 4n-4 知,R[i]-Si是連通的, 且R[i]-Si=Yi, 1 ≤i≤k-1. 注意到|Mj,j+1|-|Tj,j+1| ≥kn-1-((8n-3)-(4n-4)) ≥1, 則|E(Yj,Yj+1)| ≥1, 其中1 ≤j≤k-2,n≥3. 又由4kn-1-4 > 8n-3 可知, 在H(n,k,2)-S中, 存在一條邊e, 使得它的一個(gè)端點(diǎn)在Y0中, 另一個(gè)端點(diǎn)在Y1,Y2,Yk-2或Yk-1中. 故

情形2.24n-4 ≤|Sr|≤4n-2 ≤8n-11=8(n-1)-3.

由歸納假設(shè)可知, |V(Yr)|≥kn-1-1.

由Σi/∈{0,r}|Si|≤|T|+Σi/∈{0,r}|Si|≤|S|-|S0|-|Sr|≤5 和λ(R[i])=4n-4 ≥8 可知,R[i]-Si是連通的且R[i]-Si=Yi, 其中i/∈{0,r}. 根據(jù)2-Hamming 圖的定義,R[i]與R[i+j] (R[i-j])之間恰有kn-1條邊, 其中i/∈{0,r},j∈{1,2}. 又因?yàn)閗n-1>5 ≥|S|-|S0|-|Sr|≥|T|, 所以H(n,k,2)[∪i/∈{0,r}V(Yi)]是連通的. 以下考慮r的值.

(1) 當(dāng)r∈{1,2,k-2,k-1}時(shí), 不妨設(shè)r=1, 由3kn-1-3>5 ≥|T|可知,H(n,k,2)-S中存在一條邊e1, 使得一個(gè)端點(diǎn)在Y0中, 另一個(gè)端點(diǎn)在Y2,Yk-2或Yk-1中. 同理,H(n,k,2)-S中也存在一條邊e2, 使得一個(gè)端點(diǎn)在Y1中, 另一個(gè)端點(diǎn)在Y2,Y3或Yk-1中.

(2) 當(dāng)r/∈{1,2,k-2,k-1}時(shí), 因?yàn)?kn-1-4>5 ≥|T|, 所以H(n,k,2)-S中存在一條邊e1, 其滿足一個(gè)端點(diǎn)在Y0中,另一個(gè)端點(diǎn)在Y1,Y2,Yk-2或Yk-1中. 并且,存在一條邊e2,滿足它的一個(gè)端點(diǎn)在Yr中,另一個(gè)端點(diǎn)在Yr+1,Yr+2,Yr-2或Yr-1中.

因此, 在H(n,k,2)-S中,Y0與H(n,k,2)[∪i/∈{0,r}V(Yi)]連通, 且Yr與H(n,k,2)[∪i/∈{0,r}V(Yi)]連通. 進(jìn)一步, |V(Y)|≥kn-2. 若|V(Y)|=kn-2, 則S中至少有8n-2 條邊, 這與|S|≤8n-3 矛盾. 故|V(Y)|≥kn-1.

情形38n-10 ≤|S0|≤8n-3.

引理5[20](1)設(shè)G為一個(gè)k-正則圖, 設(shè)m是整數(shù)且滿足0 ≤m≤k-2, 則圖G是m-邊容錯(cuò)強(qiáng)Menger 邊連通的, 當(dāng)且僅當(dāng)mc(G-S)≥|V(G)|-1, 對(duì)于S?E(G), |S|≤m+k-1 都成立. (2)若G是頂點(diǎn)數(shù)不小于k+2 的k-正則圖, 則G不是(k-1)-邊容錯(cuò)強(qiáng)Menger 邊連通的.

定理2H(n,k,2)(n≥2,k≥5)是(4n-2)-邊容錯(cuò)強(qiáng)Menger 邊連通的,但不是(4n-1)-邊容錯(cuò)強(qiáng)Menger 邊連通的.

證明由引理4 和引理5 可證定理2.