路与星图的强乘积图的容错直径

来源：吉林大学学报·理学版杂志2024年第3期北京时间：

作者：岳宇翔, 李峰

单位：1. 青海师范大学 计算机学院, 西宁 810008； 2. 藏文信息处理教育部重点实验室, 西宁 810008;3. 信阳艺术职业学院 信息工程学院， 河南 信阳 464007

摘要：设路Pm与星图S1,n-1的强乘积图为G=Pm*S1,n-1. 首先, 通过归纳假设和构造内点或边不交路的方法, 结合星图的中心性, 给出图G的点容错直径Dw(G)和边容错直径D′t(G). 结果表明, 对图G中发生的任意点或边故障, 都有Dw(G)≤d(G)+2, D′t(G)≤d(G)+1. 其次, 通过顶点数和边数构造的不等关系, 给出两个极大连通图的强乘积图的点容错直径的上界, 以及两个非平凡连通图的强乘积图的边容错直径的上界.

关键词：路,星图,强乘积图,点容错直径,边容错直径