关于2连通图的容错直径与宽直径的注记

摘要：

在实时系统中,容错直径和宽直径是两个度量网络信息传输延迟和性能的重要参数.对于一般的图G,确定它的容错直径Dk困难很大,而确定它的宽直径dk却是个NPC问题,因此讨论它们之间的关系显得很重要.该文讨论了2连通图的容错直径与宽直径之间的一些性质,给出:若G是直径为2的2连通图,则d2=D2+1的充要条件为:存在两顶点u、v∈V(G),其中uv∈E(G),使得L(G)=L(G;u,v)=4或5.

关键词：连通度、直径、容错直径、宽直径

所属期刊栏目：27

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2004-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：718-720