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

Abstract

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,twith 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.

Keywords

interconnection network / fault-tolerant / LeTQs,t / hamiltonian cycle / hamiltonian path

References

[1] Lin L M, Hsieh S Y, Xu L, Zhou S M, Chen R Q. The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model. Journal of Computer System and Sciences, 2018, 95: 1–18

[2] Guo L. Reliability analysis of twisted cubes. Theoretical Computer Science, 2018, 707: 96–101

[3] Lin L M, Hsieh S Y, Chen R Q, Xu L, Lee C W. The relationship between g-restricted connectivity and g-good-neighbor fault diagnosability of general regular networks. IEEE Transactions on Reliability, 2018, 67(1): 285–296

[4] Wang D. Hamiltonian embedding in crossed cubes with failed links. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(11): 2117–2124

[5] Fan J, Jia X, Lin X. Embedding of cycles in twisted cubes with edgepancyclic. Algorithmica, 2008, 51(3): 264–282

[6] Liu Z, Fan J, Zhou J, Cheng B, Jia X. Fault-tolerant embedding of complete binary trees in locally twisted cubes. Journal of Parallel and Distributed Computing, 2017, 101: 69–78

[7] Wei C C, Hsieh S Y. h-Restricted connectivity of locally twisted cubes. Discrete Applied Mathematics, 2017, 217: 330–339

[8] Huang Y, Lin L, Wang D, Xu L. Minimum neighborhood of alternating group graphs. IEEE Access, 2019, 7: 17299–17311

[9] Zhai Y, Lin L, Xu L, Zhang X, Huang Y. The conditional diagnosability with g-good-neighbor of exchanged hypercubes. The Computer Journal, 2019, 62(5): 747–756

[10] Zhou D F, Fan J X, Lin C K, Cheng B L, Zhou J Y, Liu Z. Optimal path embedding in the exchanged crossed cube. Journal of Computer Science and Technology, 2017, 32 (3): 618–629

[11] Ren Y, Wang S. The g-good-neighbour diagnosability of locally twisted cubes. Theoretical Computer Science, 2017, 697: 91–97

[12] Yang X, Evans D J, Megson G M. The locally twisted cubes. International Journal of Computer Mathematics, 2005, 82(4): 401–413

[13] Fan W B, Fan J X, Lin C K, Wang G J, Cheng B L, Wang R C. An efficient algorithm for embedding exchanged hypercubes into grids. The Journal of Supercomputing, 2019, 75(2): 783–807

[14] Loh P K K, Hsu W J, Pan Y. The exchanged hypercube. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866–874

[15] Zhang Z, Deng Y, Min G, Xie J, Huang S. ExCCC-DCN: a highly scalable, cost-effective and energy-efficient data center structure. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(4): 1046–1060

[16] Chang J M, Chen X R, Yang J S, Wu R Y. Locally exchanged twisted cubes: connectivity and super connectivity. Information Processing Letters, 2016, 116(7): 460–466

[17] Fan W B, Fan J X, Lin C K, Wang Y, Han Y J, Wang R C. Optimally embedding 3-ary n-cubes into grids. Journal of Computer Science and Technology, 2019, 34(2): 372–387

[18] Lin L M, Xu L, Zhou S M, Hsieh S Y. The t/k-Diagnosability for regular networks. IEEE Transactions on Computers, 2016, 65(10): 3157–3170

[19] Lin L M, Xu L, Zhou S M, Hsieh S Y. The extra, restricted connectivity and conditional diagnosability of split-star networks. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2): 533–545

[20] Cheng E, Qiu K, Shen S. Diagnosability problems of the exchanged hypercube and its generalization. International Journal of Computer Mathematics: Computer Systems Theory, 2017, 2(2): 39–52

[21] Cheng E, Qiu K, Shen Z. A strong connectivity property of the generalized exchanged hypercube. Discrete Applied Mathematics, 2017, 216: 529–536

[22] Guo L, Su G, Lin W, Chen J. Fault tolerance of locally twisted cubes. Applied Mathematics and Computation, 2018, 334: 401–406

[23] Guo L, Guo X. Fault tolerance of hypercubes and folded hypercubes. The Journal of Supercomputing, 2014, 68(3): 1235–1240

[24] Wei C C, Chen C A, Hsieh S Y. Conditional (t, k)-diagnosis in regular and irregular graphs under the comparison diagnosis model. IEEE Transactions on Dependable Security and Computation, 2018, 15(2): 351–356

[25] Lin L M, Xu L, Zhou S M, Xiang Y, Trustworthiness-hypercube-based reliable communication in mobile social networks. Information Sciences, 2016, 369: 34–50

[26] Huang Y, Lin L, Wang D. On the reliability of alternating group graphbased networks. Theoretical Computer Science, 2018, 728: 9–28

[27] Li X, Liu B, Ma M, Xu J. Many-to-many disjoint paths in hypercubes with faulty vertices. Discrete Applied Mathematics, 2017, 217: 229–242

[28] Lu H, Wang F. Hamiltonian paths passing through prescribed edges in balanced hypercubes. Theoretical Computer Science, 2019, 761: 23–33

[29] Liu H, Hu X, Gao S. Hamiltonian cycles and paths in faulty twisted hypercubes. Discrete Applied Mathematics, 2019, 257: 243–249

[30] Xu X, Huang Y, Zhang P, Zhang S. Fault-tolerant vertex-pancyclicity of locally twisted cubes LTQ_n. Journal of Parallel and Distributed Computing, 2016, 88: 57–62

[31] Cheng D, Hao R. Various cycles embedding in faulty balanced hypercubes. Information Sciences, 2015, 297: 140–153

[32] Cheng C W, Hsieh S Y. Fault-tolerant cycle embedding in cartesian product graphs: edge-pancyclicity and edge-bipancyclicity with faulty edges. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(11): 2997–3011

[33] Lv Y L, Lin C K, Fan J X, Jia X H. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K_1,3-structure faults. Journal of Parallel and Distributed Computing, 2018, 120: 148–158

[34] Garey M R, Johnson D S. Computers and Intractability: a Guide to The Theory of NP-Completeness. United States of America: W. H. Freeman and Company, 1979

[35] Hsieh S Y, Wu C Y. Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults. Journal of Combinatorial Optimization, 2010, 19(1): 16–30

[36] Xu X, Zhai W, Xu J, Deng A, Yang Y. Fault-tolerant edge-pancyclicity of locally twisted cubes. Information Sciences, 2011, 181(11): 2268–2277

RIGHTS & PERMISSIONS

2020 Higher Education Press