Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n, k), that make every n - k-dimensional sub-star sub-star graph Sn-k faulty in an n-dimensional star network S-n, 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 S-n. The complexity off (n, k) is shown to be O(n(2)k) which is an improvement over the previously known upper bound of O(n(3)); this result in a special case leads to f(n, 2) = O(n(1)2), 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. (C) 2010 Elsevier Inc. All rights reserved.