On the fault‐tolerant diameter and wide diameter of ω‐connected graphs

The fault‐tolerant diameter, D k , and wide diameter, d k , are two important parameters for measuring the reliability and efficiency of interconnection networks. It is well known that for any ω‐connected graph G and any integer k , 1 ≤ k ≤ ω, we have D k ≤ d k . However, what we are interested in is how large the difference between d k and D k can be. For any 2‐connected graph G with diameter d , Flandrin and Li proved that d 2 ≤ D 2 + 1 if d = 2 and d 2 ≤ ( d − 1)( D 2 − 1) if d ≥ 3. In this article, we further prove that d 2 ≤ max{ D 2 + 1, ( d − 1)( D 2 − d ) + 2} for d ≤ ⌈( D 2 − 1)/2⌉ and d 2 ≤ max{ D 2 + 1,⌊(D 2 − 1) 2 /4⌋ + 2} for d ≥ ⌈( D 2 − 1)/2⌉ + 1, and we also show that this upper bound can be achieved. Moreover, for any ω(≥ 3)‐connected graph G , we prove that d ω ≤ D ω + 1 if D ω − 1 = 2 and d ω ≤ max{ D ω + 2,⌊(D ω ) 2 /4⌋ + 2} if D ω − 1 = 2 and D ω − 1 ≥ 3. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 88–94 2005