ON THE FAULT-DIAMETER OF THE STAR GRAPH

We derive the fault-diameter of the star graph using a combinatorial m ethod, thereby resting the previously open question of finding the exa ct value for the fault diameter of the star graph. This method is base d on counting the number of node-disjoint paths of optimal length betw een a given pair of nodes in the graph and distributing the faulty nod es among these paths in a worst-case fashion. The fault-diameter for t he n-star graph is shown to be D(n) + 1 for n greater-than-or-equal-to 7, where D(n) is the diameter of the fault-free star graph.