解國強，孟吉翔

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

0 引言

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

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

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

本文將介紹一類新的網絡結構,稱為h-Hamming 圖.h-Hamming 圖是一般的Hamming 圖的推廣,而且k-元n-立方體, Harary 圖也被包含在這個網絡當中.h-Hamming 圖是Caylay 圖, 具有簡單而豐富的拓撲性質. 本文主要探討2-Hamming 圖的強Menger 邊連通容錯性, 得到2-Hamming 圖H(n,k,2)(n≥2,k≥5)是(4n-2)-邊容錯強Menger 邊連通的, 但不是(4n-1)-邊容錯強Menger 邊連通的.

1 預備知識

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

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

定義1[7]設G為一個連通圖, 若G中的每一對頂點x,y之間都有min{dG(x),dG(y)}條邊不交的路, 則G為強Menger 邊連通圖.

定義2[7]設G為強Menger 邊連通圖,m為非負整數, 若對于任意的F?E(G)且|F|≤m,G-F仍是強Menger 邊連通的, 則G為m-邊容錯強Menger 邊連通圖.

設Γ 是一個群,S是群Γ 的一個不包含單位元的生成子集,并且滿足S=S-1. Cayley 圖C(Γ,S)是頂點集為Γ 的圖,對于Γ 中的任意兩個不同的元x和y,x與y在C(Γ,S)中相鄰當且僅當x-1y∈S. 設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, 其頂點集為{(i1,i2,···,in)|ip∈Zk,1 ≤p≤n}, 其中(i1,i2,···,in)與(j1,j2,···,jn) 相鄰當且僅當存在r(1 ≤r≤n), 使得當p/=r時, 有ip=jp, 且當p=r時, 有jp-ip∈{±1,±2,···,±h}(modk).為了方便,本文在類似的表述中省略了“(modk)”.H(1,5,2)和H(1,6,2)如圖1 所示.

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

2 邊容錯強Menger 邊連通性

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

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

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

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

證明記Sj=S∩E(R[j]), 設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中的一個最大分支為Y. 不失一般性, 設S0,S1,···,Sk-1中邊數最多的是S0, 邊數第二多的是Sr(r/=0), 邊數第三多的是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}. 進一步有R[i]-Si=Yi,其中i∈{0,1,···,k-1}. 根據2-Hamming 圖的定義可知,R[i]與R[i+j](R[i-j])之間有完美匹配并且恰有k條邊, 其中i∈{0,1,···,k-1},j∈{1,2}. 因為3k≥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. 因為R[i]與R[i+j](R[i-j])之間有完美匹配并恰有k條邊, 其中i∈{1,2,···,k-1},j∈{1,2}, 又因為2k>9, 所以是連通的. 又由4k-4>9 可知,在H(2,k,2)中存在一條邊e,并且滿足一個端點在Y0中,另一個端點在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}. 根據2-Hamming 圖的定義,R[i]與R[i+j](R[i-j])之間有完美匹配并恰有k條邊, 其中i/∈{0,r},j∈{1,2}. 又因為2k>5 ≥|S|-|S0|-|Sr|≥|T|,所以是連通的. 由引理2 可知,|V(Y0)|≥k-1 和|V(Yr)|≥k-1, 下面考慮r的值.(1) 如果r∈{1,2,k-2,k-1}. 不妨設r=1. 由3k-3>5 ≥|T|可知, 在H(2,k,2)中, 存在一條邊e1, 使得一個端點在Y0中, 另一個端點在Y2,Yk-2或Yk-1中. 并且, 在H(2,k,2)中也存在一條邊e2, 使得一個端點在Y1中, 另一個端點在Y2,Y3或Yk-1中.

(2) 如果r/∈{1,2,k-2,k-1}, 因為4k-4>5 ≥|T|, 所以在H(2,k,2)中存在一條邊e1, 使得一個端點在Y0中, 另一個端點在Y1,Y2,Yk-2或Yk-1中. 并且在H(2,k,2)中也存在一條邊e2, 使得一個端點在Yr中, 另一個端點在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.

因為|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. 因為是連通的, 又因為在H(2,k,2)中, 每個單元R[j]中的任意頂點都有4 個外鄰點, 其中j=0,r,t, 所以H(2,k,2)-S是連通的. 故|V(Y)|=k2.

情形36 ≤|S0|≤9.

情形3.1|Sr|≤3.

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

情形3.24 ≤|Sr|≤5.

由引理2 可知, |V(Yr)|≥k-1. 因為所以R[i]-Si是連通的且R[i]-Si=Yi, 其中i/∈{0,r}. 由于是連通的. 又因為在H(2,k,2)中,R[0]中的任意頂點都有4 個外鄰點, 所以是連通的. 于是,|V(Y)|≥k2-1.

情形3.3|Sr|=6.

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

情形410 ≤|S0|≤13.

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

證明用歸納法, 分別由引理2 和引理3 可知, 當n=1,2 時結論成立. 假設該結論對于n-1 時成立(其中n≥3). 記H(n,k,2)-S中的一個最大分支為Y. 下面證明結論對于n時也成立. 記Sj=S∩E(R[j]), 設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. 于是不失一般性, 設S0,S1,···,Sk-1中邊數最多的是S0, 邊數第二多的是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}. 又因為|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.

由歸納假設可知, |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, 使得它的一個端點在Y0中, 另一個端點在Y1,Y2,Yk-2或Yk-1中. 故

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

由歸納假設可知, |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}. 根據2-Hamming 圖的定義,R[i]與R[i+j] (R[i-j])之間恰有kn-1條邊, 其中i/∈{0,r},j∈{1,2}. 又因為kn-1>5 ≥|S|-|S0|-|Sr|≥|T|, 所以H(n,k,2)[∪i/∈{0,r}V(Yi)]是連通的. 以下考慮r的值.

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

(2) 當r/∈{1,2,k-2,k-1}時, 因為4kn-1-4>5 ≥|T|, 所以H(n,k,2)-S中存在一條邊e1, 其滿足一個端點在Y0中,另一個端點在Y1,Y2,Yk-2或Yk-1中. 并且,存在一條邊e2,滿足它的一個端點在Yr中,另一個端點在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)]連通. 進一步, |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)設G為一個k-正則圖, 設m是整數且滿足0 ≤m≤k-2, 則圖G是m-邊容錯強Menger 邊連通的, 當且僅當mc(G-S)≥|V(G)|-1, 對于S?E(G), |S|≤m+k-1 都成立. (2)若G是頂點數不小于k+2 的k-正則圖, 則G不是(k-1)-邊容錯強Menger 邊連通的.

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

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