Fault-tolerant hamiltonian connectedness of cycle composition networks

Tz-Liang Kueng, Cheng-Kuan Lin, Tyne Liang, Jiann-Mean Tan, Lih Hsing Hsu

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


It is important for a network to tolerate as many faults as possible. With the graph representation of an interconnection network, a k-regular hamiltonian and hamiltonian connected network is super fault-tolerant hamiltonian if it remains hamiltonian after removing up to k - 2 vertices and/or edges and remains hamiltonian connected after removing up to k - 3 vertices and/or edges. Super fault-tolerant hamiltonian networks have an optimal flavor with regard to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. For this reason, a cycle composition framework was proposed to construct a (k + 2)-regular super fault-tolerant hamiltonian network based on a collection of n k-regular super fault-tolerant hamiltonian networks containing the same number of vertices for it n >= 3 and k >= 5. This paper is aimed to emphasize that the cycle composition framework can be still applied even when k = 4. (c) 2007 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)245-256
Number of pages2
JournalApplied Mathematics and Computation
Issue number1
StatePublished - 15 Feb 2008


  • hamiltonian
  • hamiltonian connected
  • fault tolerance
  • super fault-tolerant hamiltonian

Fingerprint Dive into the research topics of 'Fault-tolerant hamiltonian connectedness of cycle composition networks'. Together they form a unique fingerprint.

Cite this