Fault Prescribed Hamiltonian-connected Ability Of K-ary N-cubes

With the development of science and increasing requirements for computer performance,parallel computer systems have been applied,born and developed rapidly.In parallel computing systems,especially large-scale and ultra-large-scale parallel computer systems,the processors are connected in a specific way and this connection is the interconnection network.The properties of the interconnection network are important to the entire parallel computer system even decisive role.For interconnection networks,there is an important type of problem that is to simulate another network on a certain network.This problem is called the embedded problem of interconnection networks.A large number of computing problems of the Internet can be used for effective simulation and research by graph embedding problems.In the parallel computing systems of interconnection network,the research on paths and circles is the most basic and important two kinds of network topologies.When designing and selecting a network,the embedding of paths and circles is a very important reference factor.In practical applications,nodes failures and communication connection failures in the network are inevitable,especially in very large-scale computer interconnection networks and computing systems.If a system can continue to perform some of its previous operations when a fault occurs,then the system is called avoidable embedding.Therefore,the fault-tolerant embedding of paths and circles in the Internet is an important reference factor that cannot be ignored.The interconnection network can usually be represented by a graph,the vertices indicate the processors,and the edges indicate the direct communication between the processors.The interconnection network can generally be represented by a graph G=(V,E),where v represents the set of nodes in the interconnection network,E represents the set of edges for direct communication in the interconnection network.In order to design a suitable interconnection network,it is necessary to study the structure of graph G.Many interconnection networks are used as the underlying topology of large-scale multiprocessor systems.k-ary n-c ube(Qnk)is the most commonly used underlying network topology in parallel computer systems.It has many excellent characteristics,it is easier to run than other networks,low latency,high bandwidth,etc.A linear forest is a graph in which every connected branch is a path.Suppose n?3,k?5 and k is odd,given a fault edge set F with at most 2n-3 edges and a linear forest L with at most 2n-3-|F| edges in k-ary n-cube,let u and v be any two distinct vertices u and v in k-ary n-cube so that u and v are not the internal vertices of a path in L and u and v are not endpoints of a path in the same time.The main contents of this proof include1.It is proved that the basic k-ary 2-cube of k-ary n-cubes network,when m,n? 5 and m,n are odd,then 2-dimensional Torus network T(m,n)is 2-prescribed hamiltonian connectivity.2.It is proved that the k-ary n-cubes network is 2n-3 tolerant prescribed hamiltonian connectivity,where n?3,k?5 and k is odd.