EDGE-BIPANCYCLICITY IN CONDITIONAL EDGE-FAULTY K-ARY N-CUBES

摘要

The class of k-ary n-cubes represents the most commonly used interconnection topology for parallel and distributed computing systems. In this paper, we consider the faulty k-ary n-cube with even k >= 4 and n >= 2 such that each vertex of the k-ary n-cube is incident with at least two healthy edges. Based on this requirement, we investigate the fault-tolerant capabilities of the k-ary n-cube with respect to the edge-bipancyclicity. We prove that in the k-ary n-cube Q(n)(k), every healthy edge is contained in fault-free cycles of even lengths from 6 to |V(Q(n)(k))|, even if the Q(n)(k) has up to 4n - 5 edge faults and our result is optimal with respect to the number of edge faults tolerated.