Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes

The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQ(s,t), which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQ(s,t) has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQ(s,t) - (f(v) + f(e)), with faulty vertices f(v) and faulty edges f(e). Firstly, we prove that an LeTQ(s,t) can tolerate up to s - 1 faulty vertices and edges when embedding a Hamiltonian cycle, for s > 2, t > 3, and s <= t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ(s,t) with up to (s - 2) faulty vertices and edges. That is, we show that LeTQ(s,t) is (s - 1)-Hamiltonian and (s - 2)-Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s - 1)-fault-tolerant Hamiltonicity and (s - 2) fault-tolerant Hamiltonian connectivity of LeTQ(s,t).

Automated summary

This paper mainly studies the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQ(s, t) - (f(v) + f(e)), proving that for s > 2, t > 3, and s <= t, an LeTQ(s, t) can tolerate up to s - 1 faulty vertices and edges when embedding a Hamiltonian cycle. Furthermore, it is also proven that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ(s, t) with up to (s - 2) faulty vertices and edges. The results demonstrate that LeTQ(s, t) is (s - 1)-Hamiltonian and (s - 2)-Hamiltonian-connected, achieving optimal (s - 1)-fault-tolerant Hamiltonicity and (s - 2) fault-tolerant Hamiltonian connectivity.