Cycle Embedding on the Edge Fault Star Graphs

Abstract

The star graph is one of the famous interconnection networks. Edge fault tolerance is an important issue for a network. And the cycle embedding problem is widely discussed in many researches. In this paper, we show that the n-dimensional star graph can be embedding cycles of even length from 6 to n! when the number of edge fault does not exceed n − 3. Since the graph is bipartite and (n − 1) regular, our result is optimal.