Conditional fault diameter of star graph networks

It is well known that star graphs are strongly resilient like the n cubes in the sense that they are optimally fault tolerant and the fault diameter is increased only by one in the presence of maximum number of allowable faults. We investigate star graphs under the conditions of forbidden faulty sets, where all the neighbors of any node cannot be faulty simultaneously; we show that under these conditions star graphs can tolerate upto (2n - 5) faulty nodes and the fault diameter is increased only by 2 in the worst case in presence of maximum number of faults. Thus, star graphs enjoy the similar property of strong resilience under forbidden faulty sets like the n-cubes. We have developed algorithms to trace the vertex disjoint paths under different conditions. (C) 1996 Academic Press, Inc.