### Abstract

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.

Original language | English |
---|---|

Title of host publication | Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010 |

Pages | 236-243 |

Number of pages | 8 |

DOIs | |

Publication status | Published - 2010 Dec 1 |

Event | International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010 - Taipei, Taiwan Duration: 2010 Sep 6 → 2010 Sep 9 |

### Publication series

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

### Other

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

Country | Taiwan |

City | Taipei |

Period | 10-09-06 → 10-09-09 |

### All Science Journal Classification (ASJC) codes

- Computational Theory and Mathematics
- Computer Science Applications

## Fingerprint Dive into the research topics of 'Super fault-tolerant hamiltonicity of product networks'. Together they form a unique fingerprint.

## Cite this

*Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010*(pp. 236-243). [5634336] (Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010). https://doi.org/10.1109/ISPA.2010.90