Super fault-tolerant hamiltonicity of product networks

Sun-Yuan Hsieh, Tsong Jie Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010
Pages236-243
Number of pages8
DOIs
Publication statusPublished - 2010 Dec 1
EventInternational Symposium on Parallel and Distributed Processing with Applications, ISPA 2010 - Taipei, Taiwan
Duration: 2010 Sep 62010 Sep 9

Publication series

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

Other

OtherInternational Symposium on Parallel and Distributed Processing with Applications, ISPA 2010
CountryTaiwan
CityTaipei
Period10-09-0610-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

    Hsieh, S-Y., & Lin, T. J. (2010). Super fault-tolerant hamiltonicity of product networks. In 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