摘要
Abstract This paper studies restricted fault diameter of the n-dimensional hypercube networks Qn (n S 2). It is shown that for arbitrary two vertices x and y with the distance d in Qn and any set F with at most 2nm3 vertices in Qn m {x,y}, if F contains neither of neighbor-sets of x and y in Qn, then the distance between x and y in Qn m F is vigen byFurthermore, the upper bounds are tight. As an immediately consequence, Qn can tolerate up to 2nm3 vertices failures and remain diameter 4 if n=3 and n+2 if nS4 provided that for each vertex x in Qn, all the neighbors of x do not fail at the same time. This improves Esfahanian's result.
Abstract This paper studies restricted fault diameter of the n-dimensional hypercube networks Qn (n S 2). It is shown that for arbitrary two vertices x and y with the distance d in Qn and any set F with at most 2nm3 vertices in Qn m {x,y}, if F contains neither of neighbor-sets of x and y in Qn, then the distance between x and y in Qn m F is vigen byFurthermore, the upper bounds are tight. As an immediately consequence, Qn can tolerate up to 2nm3 vertices failures and remain diameter 4 if n=3 and n+2 if nS4 provided that for each vertex x in Qn, all the neighbors of x do not fail at the same time. This improves Esfahanian's result.
基金
Supported by ANSF (No.01046102) and NNSF of China (No.10271114).
