Conditional fault diameter of star graph networks

Document Type



It is well known that star graphs are strongly resilient like the ncubes 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 up to (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 then-cubes. We have developed algorithms to trace the vertex disjoint paths under different conditions.


Electrical and Computer Engineering | Electrical and Electronics | Engineering | Systems and Communications


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.