A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance

Y-Chuang Chen, Yong-Zen Huang, Lih-Hsing Hsu, Jiann-Mean Tan

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Processor (vertex) faults and link (edge) faults may happen when a network is used, and it is meaningful to consider networks (graphs) with faulty processors and/or links. A k-regular Hamiltonian and Hamiltonian connected graph G is optimal fault-tolerant Hamiltonian and Hamiltonian connected if G remains Hamiltonian after removing at most k-2 vertices and/or edges and remains Hamiltonian connected after removing at most k-3 vertices and/or edges. In this paper, we investigate in constructing optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected graphs. Therefore, some of the generalized hypercubes, twisted-cubes, crossed-cubes, and Mobius cubes are optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected.
Original languageEnglish
Pages (from-to)229-238
Number of pages10
JournalJournal of Supercomputing
Volume54
Issue number2
DOIs
StatePublished - Nov 2010

Keywords

  • Fault-tolerance
  • Hamiltonicity
  • Hamiltonian connectivity
  • Generalized hypercube

Fingerprint Dive into the research topics of 'A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance'. Together they form a unique fingerprint.

  • Cite this