On Fault-Tolerant Diameter and Wide Diameter of Graphs
Xu Jun · 2002
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.