交换折叠超立方体的2-外连通度

蔡学鹏; 刘梦瑶; 杜濛雨

doi:10.13718/j.cnki.xsxb.2022.08.003

摘要: 利用2-外连通度作为评价可靠性的重要度量，对交换折叠超立方体网络EFH(s，t)的可靠性进行分析，得到了交换折叠超立方体网络的2-外连通度. 证明了EFH(s，t)的2-外连通度等于3s+1(5≤s≤t). 这个结果意味着，为了使EFH(s，t)不连通且每个分支都至少包含3个顶点，至少有3s+1个点要同时发生故障.

Abstract: The 2-extra connectivity, which is an important measure in evaluating the reliability, is utilized to analyze the reliability of exchanged folded hypercube interconnection network. Then 2-extra connectivity of exchanged folded hypercube interconnection network EFH(s, t) is obtained. We show that the 2-extra connectivity of EFH(s, t) is equal to 3s+1 for 5≤s≤t, which implies that at least 3s+1 vertices are removed to get a disconnected graph without isolated vertices(resp. edges).

Key words:

全文HTML

在本文中，术语图和网络可以互换使用. 所有的图都认为是无向的简单连通图，对于未说明的图论符号和术语，可参见文献[1-3].

设G=(V(G)，E(G))是一个图. 对于图G中的任意顶点u∈V(G)，设集合{v∈V(G)\{u}：(u，v)∈E(G)}和集合{(u，v)∈E(G)：v∈V(G)\{u}}分别表示顶点u的邻点集和邻边集，记作N_G(u)和NE_G(u). d_G(u)=|N_G(u)|称为图G中顶点u的度. 对于图G的子图K，设

分别表示子图K在G中的邻点集和邻边集.

图G的经典连通度κ(G)和边连通度λ(G)是衡量网络可靠性和容错性的两个重要参数^[4-5]. 连通度κ(G)和边连通度λ(G)越大，网络的可靠性就越高. 但是，这两个参数有明显的不足之处，比如，在互连网络的实际应用当中，与一个处理器相连接的所有处理器(链路)同时发生故障的可能性较低，所以用这两个参数衡量网络可靠性和容错性是不精确的. 为克服这些不足之处，可以通过对G-S的每一个分支强加一些限制条件来推广图G的经典连通度(边连通度)，这里S⊂V(G)(S⊂E(G)). 文献[6]首次考虑了这个问题并且提出了图G的条件连通度(边连通度)的概念.

设$\wp$是图G所具有的一种性质. 文献[6]定义了图G的条件连通度(边连通度)：如果G中存在某种点子集(边子集)，使得G删除这种点子集(边子集)后得到的图不连通，且每个连通分支都具有性质$\wp$，则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的条件连通度(边连通度)，记为κ(G∶$\wp$)(λ(G∶$\wp$)). 随后，文献[6-7]研究了下面所述的一种条件连通度(边连通度)：

设S⊂V(G)(S⊂E(G))且g是非负整数，如果G-S是不连通的，且G-S的每个连通分支中至少有g+1个顶点，则称S是G的一个R_g-割(R_g-边割). 若G存在R_g-割(R_g-边割)，则G的所有R_g-割(R_g-边割)中基数最小的R_g-割(R_g-边割)的基数称为G的g-外连通度(g-外边连通度)，记为κ_g(G)(λ_g(G)). 明显地，如果G不是完全图，则κ₀(G)=κ(G)且λ₀(G)=λ(G). 因此，g-外连通度(g-外边连通度)可以认为是经典连通度(边连通度)的一种推广形式，并且能更加精确地衡量大型并行处理系统的可靠性和容错性. 网络(图)的g-外连通度(g-外边连通度)已被许多学者研究，详细结果可参见文献[6-16]及相关文献.

在平行计算系统中，n维超立方体Q_n^[17]、n维折叠超立方体FQ_n^[16]和交叉超立方体EH(s，t)^[18]是3个重要的互连网络. 基于这3个网络，文献[19]提出了一个新的网络交换折叠超立方体EFH(s，t)，EFH(s，t)是在EH(s，t)的基础上增加了一些边获得的，并且这些边称为补边. 交换折叠超立方体有许多重要的特性，比如它有短的直径和低消费因子.

文献[20-21]探究了交换折叠超立方体EFH(s，t)的连通度和边连通度，并且证明了

文献[22]证明了

本文将探讨交换折叠超立方体EFH(s，t)的2-外连通度，最终确定了

2. 交换折叠超立方体网络的2-外连通度

定理1  设EFH(s，t)=L⊕R，对于任意的F⊆V(EFH(s，t)). 令F_L=F∩V(L)，F_R=F∩V(R). 如果|F|≤3s并且EFH(s，t)-F中既无孤立点也无孤立边，则R-F_R(或L-F_L)中每一个顶点均与L-F_L(或R-F_R)中的一个顶点连通.

证  对于任意的顶点u=1a_s-2…a₀b_t-1…b₀c∈V(R-F_R)，分以下两种情形进行讨论：

情形1  u=1a_s-2…a₀b_t-1…b₀0.

如果u_L=0a_s-2…a₀b_t-1…b₀0∉F_L或u∉F_L，则定理1得证. 因此我们假设u_L∈F_L，u∈F_L. 如果u₀=1a_s-2…a₀b_t-1…b₀1∉F_R，u_0i′=1a_s-2…a₀b_t-1…b_i′…b₀1∉F_R，u_0i′0=1a_s-2…a₀b_t-1…b_i′…b₀0∉F_R且u_0i′0(s+t)=0a_s-2…a₀b_t-1…b_i′…b₀0∉F_L(或u₀∉F_R，u₀∉F_L)，那么从u出发，总存在路径u→u₀→u_0i′→u_0i′0→u_0i′0(s+t)(或u→u₀→u₀)使其连接至L-F_L，则定理1得证. 因此我们假设u₀∈F_R. 令

如果|A| < s-1，那么存在某个i，使得u_i=1a_s-2…a_i…a₀b_t-1…b₀0∉F_R且u_i(s+t)=1a_s-2…a_i…a₀b_t-1…b₀0∉F_L(或u_i∉F_L)，则定理1得证. 因此假设|A|≥s-1.

因为EFH(s，t)-F中不存在孤立顶点，因此可令v=1a_s-2…a_i…a₀b_t-1…b₀0，使得(u，v)∈E(R-F_R). 如果v_L=0a_s-2…a_i…a₀b_t-1…b₀0∉F_L(或v∉F_L)，则定理1得证. 否则可知v_L∈F_L，v∈F_L. 如果存在v₀=1a_s-2…a_i…a₀b_t-1…b₀1∉F_R，v_0i′=1a_s-2…a_i…a₀b_t-1…b_i′…b₀1∉F_R，v_0i′0=1a_s-2…a_i… a₀b_t-1…b_i′…b₀0∉F_R，v_0i′0(s+t)=0a_s-2…a_i…a₀b_t-1…b_i′…b₀0∉F_R(或v₀∉F)，那么存在路径v→v₀→v_0i′→v_0i′0→v_0i′0(s+t)(或v→v₀→v₀)，使得u(或v)通过这条路径连接至L-F_L. 否则可假设v₀∈F_R. 令

如果|B| < s-2，那么存在某个j，使得v_j= 1a_s-2…a_i…a_j…a₀b_t-1…b₀0∉F_R且v_j(s+t)=0a_s-2…a_i…a_j…a₀b_t-1…b₀0∉F_L(或v_j∉F_L)，则定理1得证. 因此可知|B|≥s-2.

因为EFH(s，t)-F中不存在孤立边，我们令

使得(v，w)∈E(R).可以构造连接w至L-F_L的点不交路径，即路径如下：

令C={w_k，w_k(s+t)(w_k)：t+1≤k≤t+s-1，k≠i，j}，D={u_L，u，u₀，v_L，v，v₀，w_L，w，w₀}⊂F. 由于

但是在C中存在s-3对顶点使得u到L-F_L是连通的，因此至少存在一个常数k(k≠i，j)使得w_k∉F_R，w_k(s+t)∉F_R(或w_k∉F_R，w_k∉F_R). 那么u与L-F_L中的一个顶点相连接，定理1得证.

情形2  u=1a_s-2…a₀b_t-1…b₀1.

由于N_EFH(s，t)(u)∩V(L)={u}. 如果u∉F_L，则定理1得证. 因此我们可假设u∈F_L. 如果u₀=1a_s-2…a₀b_t-1…b₀0∉F_R，u_0(s+t)=0a_s-2…a₀b_t-1…b₀0∉F_R(或u₀∉F_R)，则存在一条路径，使得u连通至L-F_L，否则u₀∈F_R. 令A′={u_i′，u_i′0，u_i′0(s+t)(u_i′)：1≤i′≤t}∩F(或A′={u_i′，u_i′：1≤i′≤t}∩F)，其中u_i′=1a_s-2…a₀b_t-1…b_i′…b₀1，u_i′0=1a_s-2…a₀b_t-1…b_i′…b₀0，u_i′0(s+t)=0a_s-2…a₀b_t-1… b_i′…b₀0. 如果|A′|<t，则必定存在某一i′，使得u_i′∉F_R，u_i′0∉F_R，u_i′0(s+t)∉F_L(或u_i′∉F_R，u_i′∉F_L)，使得u连通至L-F_L. 否则|A′|≥t.

因为EFH(s，t)-F中不存在孤立点，不妨令v=1a_s-2…a₀b_t-1…b_i′…b₀1∉F_R，1≤i′≤t.，使得(u，v)∈E(EFH(s，t)-F). 如果v∉F_L，则定理1得证. 否则v∈F_L. 若v₀=1a_s-2…a₀b_t-1…b_i′…b₀0∉F_R，v_0(s+t)=0a_s-2…a₀b_t-1…b_i′…b₀0∉F_L(或v₀∉F_L)，则存在一条路径，使得u连通至L-F_L，否则v₀∈F_R. 令B′={v_j′，v_j′0，v_j′0(s+t)(v_j′)：1≤j′≤t，j′≠i′}∩F(或B′={v_j′，v_j′：1≤j′≤t，j′≠i′}∩F)，其中

若|B′| < t-1，同理可得u连通至L-F_L. 否则，|B′|≥t-1.

因为EFH(s，t)-F中不存在孤立边，令w=1a_s-2…a₀b_t-1…b_i′…b_j′…b₀1∉F_R，使得(v，w)∈E(R)，则u通过w可构造通向L-F_L的路径为

其中1≤k′≤t且k′≠i′，j′.

令C′={u₀，u，v₀，v}，由于

而u通过w可构造t-1条路径，因此至少存在1条路径使得u与L-F_L中的一个顶点相连接，定理1得证.

定理2  k₂(EFH(s，t))=3s+1，其中s≥5.

证  设P为EFH(s，t)中一条长度为2的路径，由引理7可知|N_EFH(s，t)(P)|≥3s+1. 通过EFH(s，t)的定义，EFH(s，t)-(N_EFH(s，t)(P)∪V(P))既不包含孤立顶点也不包含孤立边，因此N_EFH(s，t)(P)是EFH(s，t)的一个R₂-外割，进一步可知k₂(EFH(s，t))≤3s+1.

接下来只需证明k₂(EFH(s，t))≥3s+1，即证明对于任意的顶点集F⊆V(EFH(s，t))，当|F|=3s且不存在孤立顶点也不存在孤立边时，EFH(s，t)-F是连通的. 设EFH(s，t)=L⊕R.

方便起见，我们设

不失一般性，令|F_L|≤|F_R|，那么可知|F_L|≤$\frac{3 s}{2}$ < 2s-2，s≥5. 通过引理8，我们可知L-F_L满足下面两种情形之一：L-F_L是连通的；L-F_L有两个分支，其中一个分支是一个孤立顶点. 现在考虑下面两种情形.

情形1  L-F_L是连通的.

由定理1，可知R-F_R中任意一顶点与L-F_L中一顶点连通. 因此EFH(s，t)-F是连通的.

情形2  L-F_L有两个连通分支，其中一个是孤立点.

设u=0a_s-2…a₀b_t-1…b₀c是L-F_L中的一个孤立点，此时有|F_L|≥|N_L(u)|≥s. 接下来证明EFH(s，t)-F中的u与L-F_L-{u}是连通的. 考虑下面两种情形：

情形2.1  若u=0a_s-2…a₀b_t-1…b₀1，我们有N_EFH(s，t)(u)∩V(R)={u}. 如果u∈F_R，则u为EFH(s，t)-F中的孤立点，这与EFH(s，t)-F不存在孤立点矛盾，因此u∉F_R. 方便起见，令v=u. 如果v_s+t∉F_L，则定理2成立. 因此假设v_s+t∈F_L. 如果v₀∉F_R，v_0i′∉F_R，v_0i′0∉F_R，v_0i′0(s+t)∉F_L(或v₀∉F_R，v₀∉F_L)，则定理2得证. 因此假设v₀∈F_R. 设

如果|A| < s-1，则存在某个i，使得v_i，v_i(s+t)∉F(或v_i，v_i∉F)，则定理2得证. 因此假设|A|≥s-1.

因为EFH(s，t)-F不存在孤立边，因此存在某个i，使得(v，v_i)∈E(EFH(s，t)-F)，则u通过v_i可构造连接u到L-{u}的路径：v_i→v_ij→v_ij(s+t)，其中t+1≤j≤s+t-1，j≠i；v_i→v_i0→v_i0i′→v_i0i′0→v_i0i′0(s+t)，其中1≤i′≤t；v_i→v_i0→v_i0；v_i→v_i(s+t).

由于

且u通过v_i可构造s+1条通向L-{u}的路径，故至少存在一条路径使得u与L-F_L-{u}连通，定理2得证.

情形2.2  若u=0a_s-2…a₀b_t-1…b₀0，因为EFH(s，t)-F中不存在孤立点，故u_R=1a_s-2…a₀b_t-1…b₀0∉F或者u∉F.

若u_R，u∉F. 由EFH(s，t)的定义可知u_R和u在R中没有共同的邻点. 方便起见，设v=u_R，w=u，通过引理6，可知v(=u_R)和w(=u)在L中有两个共同的邻点，即N_L(v)∩N_L(w)={u，v(=w_R)}. 如果v(=w_R)∉F，则定理2得证. 因此假设v(=w_R)∈F. 我们可构造s+t条连接v(或w)至L-F_L-{u，v(=w_R)}的路径. 即：v(=u_R)→v_i→v_i(s+t)，其中t+1≤i≤s+t-1；v(=u_R)→v₀→v_0i′→v_0i′0→v_0i′0(s+t)，其中1≤i′≤t；w(=u)→w₀→w_0(s+t)；w(=u)→w_j′→w_j′0→w_j′0(s+t)，其中1≤j′≤t.

由于

且u通过v(或w)可构造s+t(≥2s)条通向L-{u}的路径，故至少存在一条路径使得u与L-F_L-{u}连通，定理2得证.

若u_R∉F，u∈F或者u_R∈F，u∉F. 不失一般性，假设u_R∉F，u∈F. 如果u_R∉F，则定理2得证. 因此假设u_R∈F. 如果u_R0∉F，u_R0i′∉F，u_R0i′0∉F，u_R0i′0(s+t)∉F(或u_R0∉F，u_R0∉F)，则定理2得证. 假设u_R0∈F. 因为EFH(s，t)-F中不存在孤立边，所以u_R在R中存在不属于F的邻点. 假设u_Ri∉F，其中t+1≤i≤s+t-1. 对于任意的点v∈N_R({u_R，u_Ri})，设D={v，v_L：(v，v_L)∈E(EFH(s，t))}(或D={v，v：(v，v)∈E(EFH(s，t))})，并且|D|=2s-2. 可知D⊄(N_L(u)∪{u，u_R，u_R0}). 由于

所以F中至多有2s-3个点在D中. 因此在D中至少存在一对点不属于F. 即u与L-F_L-{u}连通.

3. 小结

本文在交换折叠超立方体网络经典连通度和超连通度的基础上深入研究，进一步研究了其2-外连通度，证明了：当t≥s≥5时，k₂(EFH(s，t))=3s+1. 也就是说，EFH(s，t)中至少删除3s+1个顶点，才能得到不包含孤立顶点和孤立边的非连通图.

参考文献 (23)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

[1]	BONDY J A, MURTY U S R. Graph Theory with Applications [M]. London: Macmillan Education U K, 1976.
[2]	唐保祥, 任韩. 2类图完美对集数的计算公式[J]. 西南师范大学学报(自然科学版), 2020, 45(10): 13-15. doi: http://xbgjxt.swu.edu.cn/article/doi/10.13718/j.cnki.xsxb.2020.10.003
[3]	刘秀丽. 几类特殊图的Mycielski图的(2, 1)-全标号[J]. 西南大学学报(自然科学版), 2018, 40(12): 100-104. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-XNND201812017.htm
[4]	MA M J. The Connectivity of Exchanged Hypercubes [J]. Discrete Mathematics, Algorithms and Applications, 2010, 2(2): 213-220. doi: 10.1142/S1793830910000590
[5]	HARARY F. Conditional Connectivity [J]. Networks, 1983, 13(3): 347-357. doi: 10.1002/net.3230130303
[6]	FÀBREGA J, FIOL M A. Extraconnectivity of Graphs with Large Girth [J]. Discrete Mathematics, 1994, 127(1/2/3): 163-170. doi: 10.1016/0012-365X(92)00475-7
[7]	FÀBREGA J, FIOL M A. On the Extraconnectivity of Graphs [J]. Discrete Math, 1996, 155(1/2/3): 49-57. doi: 10.1016/0012-365X(94)00369-T
[8]	CAI X P, VUMAR E. The Super Connectivity of Folded Crossed Cubes [J]. Information Processing Letters, 2019, 142: 52-56. doi: 10.1016/j.ipl.2018.10.013
[9]	蔡学鹏, 杨伟. 折叠交叉立方体的2-外边连通度[J]. 中国科学技术大学学报, 2020, 50(2): 94-99. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-ZKJD202002002.htm
[10]	MA M J, ZHU L Y. The Super Connectivity of Exchanged Hypercubes [J]. Information Processing Letters, 2011, 111(8): 360-364. doi: 10.1016/j.ipl.2011.01.006
[11]	MA M J, LIU G Z, XU J M. The Super Connectivity of Augmented Cubes [J]. Information Processing Letters, 2008, 106(2): 59-63. doi: 10.1016/j.ipl.2007.10.005
[12]	NING W T. The Super Connectivity of Exchanged Crossed Cube [J]. Information Processing Letters, 2016, 116(2): 80-84. doi: 10.1016/j.ipl.2015.10.003
[13]	doi: https://www.researchgate.net/publication/268635794_On_restricted_connectivity_and_extra_connectivity_of_hypercubes_and_folded_hypercubes XU J M, ZHU Q, HOU X M, et al. On Restricted Connectivity and Extra Connectivity of Hypercubes and Folded Hypercubes [J]. Journal Shanghai Jiaotong University(Science), 2005, 10(2): 203-207.
[14]	ZHU Q, XU J M, HOU X M, et al. On Reliability of the Folded Hypercubes [J]. Information Sciences, 2007, 177(8): 1782-1788. doi: 10.1016/j.ins.2006.11.003
[15]	CHANG N W, TSAI C Y, HSIEH S Y. On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes [J]. IEEE Transactions on Computers, 2014, 63(6): 1594-1600. doi: 10.1109/TC.2013.10
[16]	梁家荣, 白杨, 王新阳. 评估交换超立方体网络可靠性的一种新方法[J]. 电子与信息学报, 2015, 37(3): 693-699. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201503028.htm
[17]	SAAD Y, SCHULTZ M H. Topological Properties of Hypercubes [J]. IEEE Transactions on Computers, 1988, 37(7): 867-872. doi: 10.1109/12.2234
[18]	EL-AMAWY A, LATIFI S. Properties and Performance of Folded Hypercubes [J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42. doi: 10.1109/71.80187
[19]	LOH P K K, HSU W J, PAN Y. The Exchanged Hypercube [J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874. doi: 10.1109/TPDS.2005.113
[20]	蔡学鹏, 杨伟, 任佰通, 等. 交换折叠超立方体的连通度[J]. 井冈山大学学报(自然科学版), 2019, 40(4): 8-11. doi: 10.3969/j.issn.1674-8085.2019.04.002
[21]	doi: http://en.cnki.com.cn/Article_en/CJFDTotal-JGSS201904002.htm NING W T. The Connectivity of Exchanged Folded Hypercube [J]. Parallel Processing Letters, 2020, 30(1): 1-5.
[22]	蔡学鹏. 交换折叠超立方体的2-额外边连通度[J]. 西南师范大学学报(自然科学版), 2021, 46(6): 20-26. doi: http://xbgjxt.swu.edu.cn/article/doi/10.13718/j.cnki.xsxb.2021.06.005
[23]	QI H, LI Y, LI K Q, et al. An Exchanged Folded Hypercube-Based Topology Structure for Interconnection Networks [J]. Concurrency and Computation: Practice and Experience, 2015, 27(16): 4194-4210. doi: 10.1002/cpe.3506

留言板