Hamiltonicity of Product Networks with Faulty Elements

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 δ_i be the minimum degree of G_i for i=0, 1. Given (δ_i-2)-fault Hamiltonian and (δ_i-3)-fault Hamiltonian-connected graph G_i for i=0, 1 , this study shows that the Cartesian product network G₀ ×G₁ is (δ₀+δ₁-2) -fault Hamiltonian and (δ₀+δ₁-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.