On the fault-diameter of the star graph

Document Type



We derive the fault-diameter of the star graph using a combinatorial method, thereby resting the previously open question of finding the exact value for the fault diameter of the star graph. This method is based on counting the number of node-disjoint paths of optimal length between a given pair of nodes in the graph and distributing the faulty nodes among these paths in a worst-case fashion. The fault-diameter for the n-star graph is shown to be Dn + 1 for n ⩾ 7, where Dn is the diameter of the fault-free star graph.


Cayley graphs; Computer network resources; Fault-tolerant computing; Graph theory; Routing (Computer network management)


Computer and Systems Architecture | Computer Engineering | Digital Circuits | Digital Communications and Networking | Electrical and Computer 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.

UNLV article access

Search your library