Structure Connectivity Of Locally Twisted Cubes

Interprocessor communication enabling network plays a crucial role due to the rapid technical progress in networking hardware.An interconnection network is usu-ally represented by a graph in which nodes represent processors and edges represent links between processors.The traditional connectivity is an important parameter for measuring the reliability and fault tolerance of an interconnection network.The greater the traditional connectivity is,the stronger fault-tolerant abilit,y the net-work has.However,when measuring the fault-tolerant ability of a network,it often assumes that all vertices adjacent,to the same vertex can potentially become faulty at the same time,which is almost impossible in a real mult,iprocessor system.To measure the fault tolerance of an interconnection network more accurately,Harary introduce the concept,of conditiona.l connectivity.Following this trend,g-extra con-nectivity and Rg-connectivity were explored and studied.Although there are many ways to measure the fault-tolerant ability of networks based on connectivity,these works only consider single faulty element.However in reality,nodes that are linked could affect each other,and the neighbors of a faulty node might be more vulnerable and have a higher probability of becoming faulty later.Also note that networks and subnetworks are increasingly made into chip-s in today's technology.This means that if any node/nodes on the chip become faulty,the whole chip can be considered faulty.All these motiva.te the study of fault tolerance of networks from the perspective of some structure instead of basing on individual nodes.Under t,his consideration,Lin et al.introduced the concept,of structure connectivity and substructure.connectivity of graphs,and Sabir intro-duced the concept of structure edge-connectivity and substructure edge-connectivity of graphs.Let T be a certain connected subgraph of a graph G.The T-substructure connectivity ks(G;T)(resp.T-substructure edge-connectivity ?3(G;T))of G is the minimum cardinality of a set of disjoint connected subgraphs F = ?H1,H2,…,Hm}in G,such that Hi is a connected subgraph of T for each Hi?F and G-F(resp.G-E(F))is disconnected.If Hi is isomorphic to T for each Hi ? F,we call T-structure connect,ivity k(G;T)(resp.T-structure edge-connectivity ?(G;T)).In this paper,we investigate the fault tolerant capabilities of locally twisted cubes LTQn wit,h respect to the structure-and substructure-connectivity.We not,only determine k(LTQn;T)and Ks(LTQn;T)for T ? {Pl,C2k,K1,3,K1,4} but also determine ?(LTQn;T)and ?s(LTQn;T)for T ? {P4,C4,K1,r}.