摘要
容错直径和宽直径是度量网络可靠性和有效性的重要参数 .对任何k连通图 ,它的容错直径Dk 不超过宽直径dk.论文证明d2 ≤max (d1- 1 ) (D2 - 12 d1- 1 ) +1 ,D2 +1 ;给出d1=2时d2 =D2 +1的一个充分必要条件 :d2 =3或d2 =4且达到d2
Fault-tolerant diameter D k and wide diameter d k are two important parameters for measuring reliability and efficiency of interconnection networks. It is well known that fault-tolerant diameter D k does not exceed wide diameter d k for any k-connected graph. This paper shows d 2≤max(d 1-1)(D 2-12d 1-1)+1, D 2+1, and for d 1=2. Also, a sufficient and necessary condition is given for d 2=D 2+1: d 2=3 or d 2=4 and two vertices whose wide distance between them reaches d 2 must be adjacent to each other.
基金
国家自然科学基金 (199710 86 )
中国科学院特支费
安徽省自然科学基金 (0 10 46 10 2 )资助项目
