Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k)f(n,k), that make every n-kn-k-dimensional sub-star graph Sn-kSn-k faulty in an n  -dimensional star network SnSn, has been the subject of several studies. Bounds on f(n,k)f(n,k) have already been derived, and it is known that f(n,1)=n+2f(n,1)=n+2. Here, we improve the bounds on f(n,k)f(n,k). Specifically, it is shown that f(n,k)⩽(k+1)F(n,k)f(n,k)⩽(k+1)F(n,k), where F(n,k)F(n,k) is the minimum number of faulty nodes that make every Sn-kSn-k faulty in SnSn. The complexity of f(n,k)f(n,k) is shown to be O(n2k)O(n2k) which is an improvement over the previously known upper bound of O(n3)O(n3); this result in a special case leads to f(n,2)=O(n↑2)f(n,2)=O(n↑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)f(n,1) is also introduced.