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

作     者：Weibei FAN Jianxi FAN Zhijie HAN Peng LI Yujie ZHANG Ruchuan WANG Weibei FAN;Jianxi FAN;Zhijie HAN;Peng LI;Yujie ZHANG;Ruchuan WANG

作者机构：College of ComputerNanjing University of Posts and TelecommunicationsNanjing 210023China School of Computer Science and TechnologySoochow UniversitySuzhou 215006China Jiangsu High Technology Research Key Laboratory for Wireless Sensor NetworksJiangsu ProvinceNanjing 210003China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2021年第15卷第3期

页      面：59-74页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.U1905211,61872196,61902195 and 61972272) Natural Science Foundation of Jiangsu Province(BK20200753) Natural Science Fund for Colleges and Universities in Jiangsu Province(General Program,19KJB520045),NUPTSF(NY219151,NY219131) 

主　　题：interconnection network fault-tolerant LeTQ_(s,t) hamiltonian cycle hamiltonian path 

摘      要：The foundation of information society is computer interconnection network,and the key of information exchange is communication *** interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and ***,people can build complex interconnection networks by using very large scale integration(VLSI)*** exchanged twisted cubes,denoted by(s+t+1)-dimensional LeTQ_(s,t) which combines the merits of the exchanged hypercube and the locally twisted *** has been proved that the LeTQ_(s,t) has many excellent properties for interconnection networks,such as fewer edges,lower overhead and smaller *** is an important indicator to measure the performance of interconnection *** 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 ***,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≤***,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 *** is,we show that LeTQ_(s,t) is(s-1)-Hamiltonian and(s-2)-*** 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).