2-Hamming 图的强Menger 边连通容错性∗

解国强，孟吉翔

(新疆大学数学与系统科学学院，新疆乌鲁木齐 830017)

0 引言

并行路由(即顶点不相交路径的构造) 一直是互联网络中的一个重要问题. 通过顶点间的不相交的路径不仅可以避免通信瓶颈, 提高信息传输的效率, 而且在顶点故障的情况下提供了替代路径. 随着互联网络规模的不断增加, 路由发生故障不可避免, 这与相应图的连通性密切相关.

为了更好地反映出网络的顶点不交路的容错性, 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)通常称为循环图.

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.