The Disjoint Path Cover Of Alternating Group Graphs And Split Star Graphs

The interconnection network is the connection mode between the processors in the massively computer system,which can be represented by the undirected connected graph.The vertices represent the processors in the system,and the edges represent the lines between the processors in the system.Because of their excellent topological properties,the alternating group graph and split star graph have become important interconnect networks.In the research of interconnect network,constructing point disjoint path is a very important research topic.The point disjoint path can speed up data transmission and avoid traffic congestion by providing parallel communication paths.The point disjoint routing scheme is adopted to enhance the robustness of node faults and the load balancing capability.With the continuous expansion of multiprocessor systems,computer system continuously high speed operation,the possibility of faults in the processors and the lines between the processors in a multiprocessor system is increasing,people have higher and higher requirements for network reliability at the same time.Therefore,it is very necessary to study the disjoint path cover?DPC for short?of networks with faults.At present,for the disjoint path cover of alternating group graph,the fault-tolerant one-to-one disjoint path cover has achieved certain results,but the paired many-to-many disjoint path cover has not been studied.So this paper studies the paired many-to-many disjoint path cover of the alternating group graph,and then extends the research object to the split star graph,and studies one-to-one disjoint path cover of the split star graph.This paper first studies the problem of disjoint patn cover in alternating group graphs.Considering the paired two disjoint path cover of AG₅ first,it is concluded thatAG₅ with at most one fault vertex is paired 2-DPC.Then this conclusion can be used as the basis for induction,and the following conclusions are proved by mathematical induction:Theorem 1:An arbitrary alternating group graph is paired many-to-many disjoint path cover,and for any m,1?m?n-2-f,where f is the number of fault edges or fault vertices.Secondly,this paper also studies the disjoint path cover of the split star graph.First,two new results about the Hamiltonian connectivity of the alternating group graph with faulty vertices are given.Based on these results,the disjoint path coverage of the split star graph is proved,and the following conclusions are obtained:Theorem 2:In the split star graph,there is a one-to-one m-DPC between any two different vertices,where 1?m?2n-3.