The Disjoint Path Covers In K-ary N-cube With Faulty Edges

A system's interconnection network refers to the connection way of processors of the system.An Interconnection network is usually represented by a graph,where vertices represent processors and edges represent communication links between processors.A good network can receive and transmit information and data smoothly through its vertices and edges.k-ary n-cube is an important interconnection network.Due to its good topological properties,k-ary n-cube is widely used as the interconnection network of many practical multiprocessor systems.The many-to-many disjoint path cover problem is an important issue in the field of interconnection network research.It is closely related to the data transmission.Let S = {s1,s2,…,sm} and T ?{t1,t2,…,tm} be two disjiont vertices set of order m in the graph G.If there exist m disjoint path Pi,i=1,2,…,m in graph G such that Pi connect si and t,and Ui=1 mV(Pi)?V(G),then{P1,P2,…,Pm}is said to be a path cover of G,If for any two vertex sets S and T,there excists always a m-disjoint cover(short for m-DPC)connecting S and T in G is said to be many-to-many disjoint path coverable.Along with the advancement of science and the continuous expansion of the computer system,the system of computer circuit appear more and more failure.Therefore people has higher requirement for the reliability of the network.Guarantee the information will still be able to smoothly transfer between fault systems of different processor fault-tolerance became a very critical problem.In the network topology,containing the point of failure or malfunction of figure can still guarantee trouble-free accurate and reliable information transmission between processors is crucial.To make interconnection network fault information transmission capacity,good study contains figure,on the edge of failure many-to-many don't hand in the way of covering is meaningful.In this paper,we mainly discuss many-to-many disjoint path cover problem of k-ary n-cube if it contains some faulty deges.For the k-ary n-cube,we mainly study that when it contains at most 2n-4 faulty edges,then k-ary n-cube is 2-DPC;F or the k-ary 3 cube,we mainly study that,when it contains at most 3 faulty edges,then k-ary 3 cube is 2-DPC,And the fault edges number has reached the upper bound;For the k-ary n-cube,we mainly study the many-to-many disjoint path cover promble:Let F is the collection of the faulty edges of the k-ary n-cube,and Mm={ui,V,}i=1m is a collection of the vertces,when |F|?2n-m-2,the k-ary n-cube is m-DPC.there n?2 and even k?4,1?m?2n-2.