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.
- hamiltonian connected
- fault tolerance
- super fault-tolerant hamiltonian
Kueng, T-L., Lin, C-K., Liang, T., Tan, J-M., & Hsu, L. H. (2008). Fault-tolerant hamiltonian connectedness of cycle composition networks. Applied Mathematics and Computation, 196(1), 245-256. https://doi.org/10.1016/j.amc.2007.05.055