Edge Fault-tolerant Spanning Connectivity Of The3-ary N-cube And Edge Fault-tolerant2-disjoint Path Cover Of The Hypercube

One of the centural issues in interconnection networks is finding vertex-disjoint paths，which can be used as paralled paths for an efficient data routing among nodes. The problem ofone-to-one disjoint path cover （also called spanning connectivity） and of many-to-manydisjoint path cover of a network recently received considerable attention since it has someimportant applications.The hypercubeQ_n and the3-ary n-cubeQ_n³n are popular networks. Fault-tolerance of anetwork is important. In this thesis we investigate the problem of edge fault-tolerant spanningconnectivity ofQ_n³n and the problem of edge fault-tolerant2-disjoint path cover ofQ_n. Thefollowing rsults are obtained.Theorem1: LetQ_n³n be a3-ary n-cube with n≥2, and F be any subset of edges withf=F≤2n3. For any w with1≤w≤2n f, and for any pair of vertices u and v,there exist w internally vertex-disjoint paths between u and v such that these w pathscontain all vertices ofQ_n³Theorem2: LetQ_n be an n-cube with n≥4, andF be any subset of edges withF≤n3. Assume thatx1,x2,y1,y2are any four vertices inQ_n such thatx1andy₁belong to a partite set, andx2andy2belong to the another partite set inQ_n. Then thereexist two vertex-disjoint fault-free pathsP1betweenx1andy1andP2betweenx2andy2such that V （P₁） UV （P₂）=V （Q_n）. Moreover, the number n3of faulty edgestoleranted is sharp.