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

Fault Diameter of Strong Product Graph of Path and Star Graph

作　　者：岳宇翔 李峰[1] YUE Yuxiang;LI Feng(College of Computer,Qinghai Normal University,Xining 810008,China;The State Key Laboratory of Tibetan Intelligent Information Processing and Application,Xining 810008,China;College of Information Engineering,Xinyang Vocational College of Art,Xinyang 464007,Henan Province,China)

机构地区：[1]青海师范大学计算机学院,西宁810008 [2]藏文信息处理教育部重点实验室,西宁810008 [3]信阳艺术职业学院信息工程学院,河南信阳464007

出　　处：《吉林大学学报（理学版）》2024年第3期487-496,共10页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:11551002);青海省自然科学基金(批准号:2019-ZJ-2093).

摘　　要：设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.Let the strong product graph of path P_(m)and star graph S_(1,n-1)be G=P_(m)S_(1,n-1).Firstly,by inducing assumptions and constructing internally vertex or edge disjoint paths,combined with the centrality of star graph,the vertex fault diameter D_(w)(G)and edge fault diameter D′t(G)of the graph G were given.The results show that for any vertex or edge fault in the graph G,there holds D_(w)(G)≤d(G)+2 and D′t(G)≤d(G)+1.Secondly,through the unequal relation between the number of vertices and the number of edges,the upper bound of the vertex fault diameter of the strong product graph of two maximally connected graphs and the upper bound of the edge fault diameter of the strong product graph of two nontrivial connected graph were given.

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

分 类 号：O157.5[理学—数学]