由换位无三角形单圈图生成的 Cayley 图在 PMC 和 MM?模型下的循环可诊断性

《Discrete Applied Mathematics》:The cyclic diagnosability of Cayley graphs generated by transposition triangle-free unicyclic graphs under the PMC and MM? models

【字体: 大 中 小 】 时间:2026年09月27日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   摘要 可诊断性是评估多处理器系统可靠性和自诊断能力的关键参数。作为传统可诊断性的高级扩展,循环可诊断性已被提出,以实现互联网络诊断能力的更全面评估。本文证明,在PMC和MM?模型下,当n≥11时,由无三角形单圈图生成的Cayley图的循环可诊断性为5n?10。 引言 在

  

摘要

可诊断性是评估多处理器系统可靠性和自诊断能力的关键参数。作为传统可诊断性的高级扩展,循环可诊断性已被提出,以实现互联网络诊断能力的更全面评估。本文证明,在PMC和MM?模型下,当n≥11时,由无三角形单圈图生成的Cayley图的循环可诊断性为5n?10。

引言

在大规模并行计算环境中,多处理器系统因其高性能和可靠性要求而被广泛应用于科学计算、数据分析和人工智能等领域。随着系统规模不断扩大,处理器节点故障的概率显著增加。因此,故障诊断能力已成为评估多处理器系统可靠性的重要指标之一。通常,多处理器系统可以被抽象为一个无向图,其中顶点代表处理器,边代表处理器之间的测试或通信关系。

系统级故障诊断的核心在于通过适当的测试机制识别故障处理器。为此,研究人员提出了各种系统级诊断测试模型。Preparata、Metze和Chien[11]提出了PMC模型,这是最早的系统级诊断模型之一,也是最广泛使用的经典模型之一。Maeng和Malek[7]、[8]提出了比较模型,即MM模型。随后,Sengupta和Dahbura[12]改进了MM模型并提出了MM?模型,该模型作为PMC模型局限性的重要补充。

传统多处理器系统的可诊断性仅关注可识别的最大故障处理器数量,而不考虑故障发生后剩余网络的结构。为了更好地刻画系统在特定故障场景下的容错能力,研究人员引入了各种广义可诊断性概念。Lai等人[5]提出了条件可诊断性的概念,其限制条件为任何故障集不能包含图中任意顶点的所有邻居。Peng等人[10]引入了g-好邻居可诊断性,要求系统中每个无故障顶点至少有g个无故障邻居。Zhang和Yang[18]提出了g-额外可诊断性,要求每个剩余分量至少包含g+1个顶点。随后,Zhang等人[17]进一步提出了g-分量可诊断性,要求剩余图至少包含g个分量。基于这些关于可诊断性的研究,Zhang等人[20]引入了循环可诊断性的概念,要求在移除故障顶点后,至少有两个剩余分量各自包含一个环。

目前,循环可诊断性的研究已取得显著进展。例如,Zhang等人[20]建立了循环可诊断性与正则网络中循环连通性之间的度量关系,并据此确定了超立方体Q?、局部扭超立方体LTQ?和交替群网络AN?的循环可诊断性。迄今为止,研究人员已确定了n维平衡超立方体BHN、k维DCell网络Dk,n、折叠超立方体FQ?、星形图Sn以及PMC和MM?模型下由换位树T?生成的Cayley图的循环可诊断性;更多细节参见[4]、[9]、[14]、[21]、[22]。

由换位单圈图生成的Cayley图是顶点传递的,具有优异的对称性和较小的直径。它们可以通过增加顶点数n灵活扩展,适合构建大规模多处理器系统。这类图的许多性质已被广泛研究。例如,Wang和Zhou[15]证明了这些Cayley图的广义3-连通度在n≥4时为n?1。Gu等人[3]研究了此类图在PMC和MM?模型下的条件可诊断性。Tian等人[13]表明,由无三角形单圈图生成的Cayley图的循环连通度为4n?8。

本文研究PMC和MM?模型下由无三角形单圈图生成的Cayley图的循环可诊断性。我们得出结论:当n≥11时,由无三角形单圈图生成的Cayley图的循环可诊断性为5n?10。

本文其余部分组织如下。第2节介绍预备知识。第3节分析由无三角形单圈图生成的Cayley图的循环可诊断性结构,并确定其在PMC和MM?模型下的循环可诊断性。第4节总结全文。

预备知识

首先介绍本文中将使用的一些符号和结果。设G=(V(G), E(G))为一个简单有限无向图,其中V(G)为其顶点集,E(G)为其边集。对于任意顶点v∈V(G),N_G(v)={u∈V(G)|(u,v)∈E(G)}是G中与v相邻的所有顶点的集合,N_G(v)的基数为v的度,记为d_G(v)。正则图是每个顶点具有相同度的图,度为k的正则图称为k-正则图。

主要结果

本节研究由换位无三角形单圈图生成的Cayley图的循环可诊断性。我们注意到,UG?之前用于表示更广义的由换位单圈图生成的Cayley图类。在本文其余部分,我们精化此记号,使其专门指代由换位无三角形单圈图生成的Cayley图。这一定义将在后续所有部分中一致使用。

结论

本文建立了如下结论:在PMC和MM?模型下,当n≥11时,由无三角形换位单圈图生成的Cayley图的循环可诊断性等于5n?10。一个自然且有趣的问题随之产生:在PMC和MM?模型下,由一般换位单圈图(无无三角形限制)生成的Cayley图的循环可诊断性是什么?

丁嘉璐 | 李彩霞 | 李品山 | 金伟
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号