TY - GEN

T1 - Super fault-tolerant hamiltonicity of product networks

AU - Hsieh, Sun-Yuan

AU - Lin, Tsong Jie

PY - 2010/12/1

Y1 - 2010/12/1

N2 - A graph G is called 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 δ(G) be the minimum degree of G. Given a (δ(G) - 2)-fault Hamiltonian/ (δ(G) - 3)-fault Hamiltonian-connected graph G and a (δ(H) - 2)-fault Hamiltonian/ (δ(H)-3)-fault Hamiltonian-connected graph H, we show that the Cartesian product network G x H is (δ(G)+δ(H)-2)-fault Hamiltonian and (δ(G)+δ(H)-3)-fault Hamiltonian-connected. We then apply our 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. We also demonstrate that our results are worst-case optimal with respect to the number of faults tolerated.

AB - A graph G is called 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 δ(G) be the minimum degree of G. Given a (δ(G) - 2)-fault Hamiltonian/ (δ(G) - 3)-fault Hamiltonian-connected graph G and a (δ(H) - 2)-fault Hamiltonian/ (δ(H)-3)-fault Hamiltonian-connected graph H, we show that the Cartesian product network G x H is (δ(G)+δ(H)-2)-fault Hamiltonian and (δ(G)+δ(H)-3)-fault Hamiltonian-connected. We then apply our 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. We also demonstrate that our results are worst-case optimal with respect to the number of faults tolerated.

UR - http://www.scopus.com/inward/record.url?scp=79952094078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952094078&partnerID=8YFLogxK

U2 - 10.1109/ISPA.2010.90

DO - 10.1109/ISPA.2010.90

M3 - Conference contribution

AN - SCOPUS:79952094078

SN - 9780769541907

T3 - Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010

SP - 236

EP - 243

BT - Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010

T2 - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010

Y2 - 6 September 2010 through 9 September 2010

ER -