Fault-Tolerant Cycle Embedding in Cartesian Product Graphs: Edge-Pancyclicity and Edge-Bipancyclicity with Faulty Edges
Chia-Wen Cheng, Sun‐Yuan Hsieh · IEEE Transactions on Parallel and Distributed Systems · 2014
A graph G is called k-edge-fault edge-bipancyclic (k-edge-fault edge-r-pancyclic) if after deleting k edges from G, every edge in the resulting graph lies in a cycle of every even length from 4 to IV (G)I (a cycle of every length from r to IV(G)I), inclusively. In this paper, given two graphs G and H, which satisfy some specific properties, the edge-fault edge-bipancyclicity and edge-fault edge-r-pancyclicity (r is decided on the properties of G and H) of Cartesian product graphs G x Hare efficiently evaluated. The obtained results are applied to two multiprocessor systems, the nearest neighbor mesh hypercubes and generalized hypercubes, both of which belong to Cartesian product graphs.