Hamiltonicity of Product Networks with Faulty Elements
Chia‐Wei Lee, Tsong‐Jie Lin, Sun‐Yuan Hsieh · IEEE Transactions on Parallel and Distributed Systems · 2013
A graph$G$is$k$-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most$k$vertices and/or edges from$G$, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let$\delta_{i}$be the minimum degree of$G_{i}$for$i=0$, 1. Given$(\delta_{i}-2)$-fault Hamiltonian and$(\delta_{i}-3)$-fault Hamiltonian-connected graph$G_{i}$for$i=0, 1$, this study shows that the Cartesian product network$G_{0} \times G_{1}$is$(\delta_{0}+\delta_{1}-2)$-fault Hamiltonian and$(\delta_{0}+\delta_{1}-3)$-fault Hamiltonian-connected. We then apply the result to determine the fault-tolerant Hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. This study also demonstrates that these results are worst-case optimal with respect to the number of faults tolerated.