The Edge-fault-tolerant Path Embedding In Three Classes Of Networks

Panconnectivity and disjoint-path cover have important applications in interconnectionnetworks. Panconnectivity implies the embedding of paths of various lengths in networks.Hence, it can effectively simulate many algorithms designed on linear arrays. Disjoint-pathcover implies that every node can participate paralled-path data routing.The folded hypercubeFQ_n、k-ary n-cubeQ knand complete multipartite graphKn, n,L,narethree important network topology structures that have widely been used in parallel processingand distributed computing system. In this paper, we study the disjoint-paths covers in foldedhypercubeFQ_n with faulty edges and k-ary n-cubeQ kn, and the panconnectivity of completemultipartite graphKn, n,L,n.In this thesis, our main results are as follows.1. If n （n≥3）is odd and1≤k≤n,F_e denotes a set of faulty edges inFQ_n withF_e≤n k, and let S （resp., T） be a set of k black vertices（resp., white vertices）inFQ_n, then there exists a many-to-many k disjoint fault-free （S,T）-path cover in inFQ_n F_e. Moreover, the upper bound ofF_e is optimal.2. Assume thatx₁、y₁、x₁andy2are any four distinct vertices inQ6n, where n≥2,x₁andx₁are two black vertices andy₁andy2are two white vertices, then there existtwo vertex-disjoint pathsP1betweenx₁andy₁andP2betweenx₁andy2such thatV （P1）UV（P）=V（Q62n）.3. LetK n,n（n≥2） be a complete bipartite graph,F_e denote a set of faulty edgesinFQ_n with F_e≤n2, thenK n,n F_eis bipanconnected. Moreover, the number n2offaulty edges tolerated is optimal.4. The complete k-partite graphKn, n,L,n（k≥3）is panconnected.