Cycle embedding in star graphs with edge faults

摘要

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