关于4连通图的容错直径和宽直径的一个新结果

A New Result on Fault-tolerant Diameter and Wide Diameter of 4-Connected Graphs

容错直径Dk可以度量容错网络中数据传输延迟,宽直径dk能度量网络的容错度和传输效率,因此容错直径和宽直径是设计和评估网络性能的重要参数.对于任意k连通图,它的容错直径Dk不超过宽直径Dk.证明了当D2≥3时,d4≤3(D2-1)(D3-1)[2(D3-1)(D4-1)-5]-3/2D22+3/2D2+1.

Fault - tolerant diameter Dk can measure network fault - tolerant data transmission delay, and width diam- eter dk can be metric fault - tolerant wrong degree and transsferring efficiency. Therefore, fault - tolerant di- ameter Dk and wide diameter dk are important parameters on design and appraisal of network performance. It is well known that fault - tolerant diameter De does not exceed wide diameter de for any k - connected graph .This paper shows ,d4≤3（D2-1）（D3-1）[2（D3-1）（D4-1）-5]-3/2D2^2＋3/2D2＋1