Hamiltonian Path Of N-dimensional Torus Network With Faulty Edges

With the increasing amount of information and the deepening of scientific and technological research,people have higher and higher requirements on the performance of computing and storage of computers.Therefore,large-scale parallel computer system comes into being.Interconnection network is a connection between processors in a large-scale computer system,which can be represented by an undirected connection graph.Vertices in the graph represent processors in the system,and edges represent the lines between processors in the system.In massively parallel computer system,the interconnection network plays an important and even decisive role in the stable operation of the whole parallel computer system.With the continuous expansion of the scale of computer system,the probability of failure of each component and component is more and more large,so people have higher and higher requirements for fault tolerance and reliability of interconnection network.In order to maintain good information transmission ability of fault interconnection network,it is significant to study the existence of Hamilton circles and paths of interconnection network with fault edges.Torus network is the most widely used distributed computer system interconnection network.It contains many advantages,such as simple network structure;regularity,symmetry,expansibility,path diversity and other characteristics.Many parallel and distributed systems that have been put into commercial application are based on the network to form their connection mode.At present,some achievements have been made in the research of fault-tolerant Hamilton and Hamilton connectivity for networks.In order to increase the upper bound on the number of faults allowed by Hamiltonicity,various conditional fault assumptions have been proposed,among which the most common one is the assumption that the occurrence of fault will not cause the network to produce vertex of degree one.However,the failure situation of generating vertex of degree one in the network does exist,so it is meaningful to study the fault interconnection network with vertex of degree one.The existence of vertex of degree one makes the network as a whole not Hamiltonian and Hamiltonian connectivity,but it is still Hamiltonian between special point pairs.In this paper,we take the torus network as the research object,and discuss the existence problem of Hamilton path in the case of vertex of degree one.This paper first studies the two-dimensional torus network.In this paper,the existence problems of Hamiltonian paths of two-dimensional torus networks with fault edges are studied under two different conditions by using special subdivision method:(1)contains a vertex of degree one;(2)contains two vertices of degree one.So we end up with three related theorems.Secondly,this paper extends the above conclusions.Based on the existence of fault-tolerant Hamilton paths in two-dimensional torus networks,we extend the relevant results to n-dimensional torus networks with fault edges by mathematical induction,and determine a new upper bound on the number of faults that can be allowed to maintain Hamilton connectivity under the current conditions.Suppose F is the fault edge set of a bipartite graph torus network Torus(k1,k2,…,kn),where k1,k2,…,kn are even and n? 2,the main conclusions are as follows:(1)Suppose k1,k2,…,kn? 4,|F| ?4n-4,u and v are not in the same part.If u is the vertex of degree one in the Torus(k1,k2,…,kn)-F and(u,v)? E(Torus(k1,k2,…,kn)-F),then there is a Hamiltonian paths from u to v in the Torus(k1,k2,…,kn)-F.(2)If k1,k2…,kn ? 6,|F| ? 6n-7,u is the only vertex of degree one in the Torus(k1,k2,…,kn)-F,then Hamiltonian paths exist that go from u to at least 2n-2 adjacent vertices of u in the Torus(k1,k2,…,kn).(3)Suppose k1,k2,…kn? 4.|F| ? 6n-6,if u and v are the vertex of degree one in the Torus(k1,k2,…,kn)-F and(u,v)E F,then there is a Hamiltonian paths from u to v in the Torus(k1,k2,…,kn)-F.