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

摘要

设路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.其次，通过顶点数和边数构造的不等关系，给出两个极大连通图的强乘积图的点容错直径的上界，以及两个非平凡连通图的强乘积图的边容错直径的上界.

关键词

路 / 星图 / 强乘积图 / 点容错直径 / 边容错直径