On the Fault-diameter of the Star Graph

Authors

Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

6-11-1993

Publication Title

Information Processing Letters

Volume

46

First page number:

143

Last page number:

150

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 D_n + 1 for n ⩾ 7, where D_n is the diameter of the fault-free star graph.

Keywords

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

Disciplines

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

Language

English

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.

Repository Citation

Latifi, S. (1993). On the Fault-diameter of the Star Graph. Information Processing Letters, 46 143-150.