Title

On the fault-diameter of the star graph

Document Type

Article

Abstract

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.

Disciplines

Computer and Systems Architecture | Computer Engineering | Digital Circuits | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications

Permissions

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.