Improving bounds on link failure tolerance of the star graph

Document Type



Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph Sn-k faulty in an n-dimensional star network Sn, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)⩽(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every Sn-k faulty in Sn. The complexity of f(n,k) is shown to be O(n2k) which is an improvement over the previously known upper bound of O(n3); this result in a special case leads to f(n,2)=O(n2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.


Digital Communications and Networking | Electrical and Computer Engineering | OS and Networks | 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.