Robustness of Star Graph network Under Link Failure

Authors

Shahram Latifi, University of Nevada, Las VegasFollow
Ebrahim Saberinia, University of Nevada, Las VegasFollow
Xiaolong Wu, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

2-1-2008

Publication Title

Information Sciences

Volume

178

Issue

3

First page number:

802

Last page number:

806

Abstract

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.

Keywords

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

Disciplines

Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Signal Processing | 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., Saberinia, E., Wu, X. (2008). Robustness of Star Graph network Under Link Failure. Information Sciences, 178(3), 802-806.