这是关于笛卡尔积幂图 (K9?C9)n 在强门格尔边连通性和分量边连通性上的链路容错性的研究

《Discrete Applied Mathematics》：Link fault tolerance of the Cartesian product power graph (K9?C9)n on strongly Menger-edge-connectivity and component edge-connectivity

本文深入研究了作为多处理器系统拓扑结构的笛卡尔积幂图(K9?C9)n的两种条件边连通性参数。基于词典序为其边等周问题提供的优化解，文章确定了该网络结构具有F-强门格尔边连通性(FSMEC)的充分条件，并精确计算了其强门格尔边连通性数值smλ6t((K9?C9)n)=6(n?t)9t?6n。同时，文章还证明了其(r+1)-分量边连通性cλr+1((K9?C9)n)=6nr?exr((K9?C9)n)/2。这些结果为评估和优化大规模高性能计算互连网络的容错性和可靠性提供了重要的理论依据。

　　

亮点

• •
  在互连网络的边等周问题中，词典序为笛卡尔积幂图提供了最优解。
• •
  我们研究了两种条件边连通性作为评估互连网络容错性和可靠性的参数，即(r+1)-分量边连通性和强门格尔边连通性。

关键词

互连网络； (r+1)-分量边连通性； 强门格尔边连通性； 笛卡尔积图

1. 引言

高性能计算是通过并行处理和互连技术连接多个计算节点，以快速、可靠、高效地运行高级应用的过程[7]。它可以为标准桌面计算机解决商业、工程或科学领域的复杂问题提供更高的性能，并已成为解决国家安全、经济发展、科学研究和其它领域许多关键问题的重要工具[16]。如今，它已成为解决科学研究和经济增长众多重要问题的关键工具。在设计构建并行计算机时，使用互连网络连接所有处理元件至关重要。互连网络被建模为无向图G=(V(G), E(G))，其中处理器和通信链路分别代表顶点和边。

关于图的定义和符号，我们遵循文献[5]的工作。考虑G是一个无向简单图。设X是V(G)的一个子集。我们用Xˉ=V(G)?X表示其补集。X在G中的基数通常表示为|X|。由X诱导的子图记作G[X]，其顶点集为X，边集由G中所有端点都在X内的边组成。对于图G中的一个顶点u，我们用N_G(u)表示u在G中的所有邻居，用deg_G(u)表示N_G(u)的基数。对于集合F?E(G)，我们用G?F表示从G中删除F后得到的图。对于X,Y?V(G)，我们用[X,Y]_G表示G中一个端点在X、另一个端点在Y的所有边的集合，即[X,Y]_G={ab∈E(G)∣a∈X, b∈Y}。由任意m个顶点诱导的子图的最大度和表示为ex_m(G)。设ξ_m(G)=min{|[X,Xˉ]_G|: X?V(G) 满足 |X|=m≤?|V(G)|/2?， 且G[X]和G[Xˉ]都连通}。

在考虑互连网络的设计和运行时，可靠性和效率不容忽视。更多的不相交路径意味着更多的信息传输链路，这显著提高了互连网络的效率。因此，在发生边故障时，研究互连网络的边连通性λ(G)尤其重要。图G的边连通性的一个基本定义是(u, v)-路径的最大边不相交路径数集合中的最小值，其中u, v∈V(G)。1984年，Sampathkumar[17]引入了连通图G的r-分量边连通性概念，为互连网络的容错性提供了一个更精细的参数。如果存在，连通图G的子集F被称为G的一个r-分量边割，如果在G?F中至少有r个连通分量。G的r-分量边连通性，记作cλ_r(G)，是G的任何r-分量边割的最小基数。Boesch和Chen[4]研究了r-分量边连通性的几个性质，并基于图G的最小度和度序列建立了其下界。近年来，r-分量边连通性的概念引起了高度关注。例如，超立方体Q_n[25]，增强立方体AQ_n[23]，BC网络B_n[12]，3元n-立方体K₃ⁿ[19]，局部扭曲立方体LTQ_n[18]，汉明图K_Lⁿ[20]等。

众所周知，λ(G)≤δ(G)，这意味着边连通性的大小受最小度的限制。随着互连网络的扩展，最大度与最小度之间的差异将逐渐扩大，这导致边连通性无法很好地反映度数较大顶点的连通性。2003年，Oh等人[14]提出了强门格尔边连通性的概念：如果对于图G中的每对顶点u和v，在u和v之间存在min{deg_G(u), deg_G(v)}条不相交路径，则称连通图G为强门格尔边连通的（简称SM-λ）。评估网络的容错性至关重要，因为实际网络中可能存在故障。2018年，Cheng等人[6]为带有故障的图引入了强门格尔边连通性的定义。如果对于任意边集F?E(G)且|F|≤m，G?F保留SM-λ性质，则称图G是m-边故障容忍强门格尔连通的。如果故障数量不是过多，假设它们均匀随机分布，则每条故障边关联到单个顶点的可能性不大。基于这些原因，2018年，He等人[8]提出了m-阶t强门格尔边连通性的定义以及最大整数m，记作sm_λ^t(G)。给定一个固定整数t，令F是连通图G的一个满足限制条件δ(G?F)≥t的边集。那么边集F是一个t阶条件故障边集。如果图G中的每一对顶点u和v在G?F中都由min{deg_G?F(u), deg_G?F(v)}条边不相交的路径连接，则图G被称为是F-强门格尔边连通的（简称F-SMEC）且阶为t。如果对于每个满足|F|≤m且F是t阶条件边故障集的F，图G是F-SMEC且阶为t，则称图G是m-阶t强门格尔边连通的。

F-强门格尔边连通性已被多位研究者用于研究多种互连网络，如下所示：对于Q_n，Qiao和Yang[15]证明了对于n≥4，有sm_λ²(Q_n)=(2n?4)；对于平衡超立方体BH_n，Li和Xu[11]证明了对于n≥2，有sm_λ²(BH_n)=(6n?8)；对于B_n，Liu等人[13]得到了对于n≥3且1≤t≤n?2，有sm_λ^t(B_n)=2^t(n?t)?n；对于折叠超立方体FQ_n，Zhao和Li[24]证明了对于1≤t≤n?2且n≥4，有sm_λ^t(FQ_n)=2^t(n?t+1)?(n+1)；最近，Zhang等人[22]证明了对于1≤t≤n?2且n≥3，有sm_λ^(L?1)t(K_Lⁿ)=L^t(n?t)(L?1)?(L?1)n；对于完全约瑟夫立方体CJC_n，Huang等人[9]确定了对于4≤t≤n?2且n≥6，有sm_λ^t(CJC_n)=2^t(n?t+1)?(n+2)。

笛卡尔积幂图(K₉?C₉)ⁿ作为一种新型互连网络，在研究领域引起了广泛关注。2018年，Bezrukov等人[3]利用词典序找到了笛卡尔积幂图(K₉?C₉)ⁿ边等周问题的最优解。2021年，Afiya和Rajesh[1]探索了(K₉?C₉)ⁿ的泛环性。2023年，Afiya和Rajesh[2]确定了将(K₉?C₉)ⁿ嵌入大小为9ⁿ的路径、香蕉树和鞭炮树的最优线长。本文重点关注笛卡尔积幂图(K₉?C₉)ⁿ的两个参数：(r+1)-分量边连通性cλ_r+1((K₉?C₉)ⁿ)和6t阶的F-强门格尔边连通性，记作sm_λ^6t((K₉?C₉)ⁿ)。我们证明了对于0≤t≤n?2且n≥3，有sm_λ^6t((K₉?C₉)ⁿ)=6(n?t)9^t?6n。此外，我们还证明了对于r≤9^?n/2?且n≥4，有cλ_r+1((K₉?C₉)ⁿ)=6nr?ex_r((K₉?C₉)ⁿ)/2。

论文的其余部分组织如下。在第2节中，我们阐述了笛卡尔积幂图(K₉?C₉)ⁿ的一些基本结构。在第3节中，我们分析了(K₉?C₉)ⁿ的边等周问题相关函数ξ_m((K₉?C₉)ⁿ)的层次单调性和迭代性，以及函数ex_m((K₉?C₉)ⁿ)的一些性质。在第4节中，我们确立了(K₉?C₉)ⁿ的6t阶F-强门格尔边连通性的精确值。