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

Fault Diameter of Strong Product Graph of Path and Star Graph

设路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.