Path Embeddings In Faulty 4-ary N-cubes

Theκ-ary n-cube is one of the most popular interconnection networks for parallel and distributed systems.Theκ-ary n-cube is denoted by Qnκ(κ≥2,n≥1).The set of vertices V(Qnκ)={u0u1···un-1:0≤ui≤κ-1,0≤i≤n-1}.Two vertices u=u0u1···un-1 and v=v0v1···vn-1 are adjacent if and only if there exists an integer j∈{0,1,···,n-1} such that uj=uj±1(modκ)and ui=vi for every i∈{0,1,···,n-1}＼{j}.In multiprocessor systems,failures in networks are inevitable.If a network with faulty elements still have some good properties,then the network is faulty-tolerant.The graph embedding is a technique that maps a guest graph into host graph. Many graph em-beddings take paths and cycles as guest graphs because they are the common structures used to model linear arrays in parallel processing.In this paper,we study the problem of embedding paths into faulty 4-ary n-cubes.The article is divided into three chapters:In Chapter 1,we introduce some useful basic concepts.In Chapter 2,we study the problem of embedding paths into 4-ary n-cubes with faulty vertices.Let f be the number of faulty vertices with f≤n-1.The main results are as follows:(1)Let u,v∈V(Qn4).If u and v are adjacent,then there exists a fault-free(u,v) path of every odd length l from 2n-1 to 4n-2f-1.(2)Let u,v∈V(Qn4).If there exists an integer j∈{0,1,···,n-1}such that uj=vj±2(mod 4)and ui=vifor every i∈{0,1,···,n-1}＼{j},then there exists a fault-free(u,v)path of every even length l from 2n to 4n-2f-2.In Chapter 3,we study the problem of embedding paths into 4-ary n-cubes with faulty vertices or edges.Let Fv be the set of faulty vertices and Fe be the set of faulty edges and let F=Fv∪Fe.Suppose that |F|≤2n-3.The main results are as follows:(1)Let u,v∈V(Qn4).If u and v are adjacent,then there exists a fault-free(u,v) path of every odd length l from 1 to 4n-2|Fv|-1.(2)Let u,v∈V(Qn4).If there exists an integer j∈{0,1,···,n-1}such that uj=vj±2(mod 4) and ui=vi for every i∈{0,1,···,n-1}＼{j},then there exists a fault-free(u,v)path of every even length l from 2 to 4n-2|Fv|-2.(3)Let.u,v∈V(Qn4).If there exist two integers i,j∈{0,1,···,n-1}such that ui=vi±1(mod 4),uj=vj±1(mod 4)and um=vm for every m∈{0,1,···,n-1}＼{i,j}, then there exists a fault-free(u,v)path of every even length l from 4 to 4n -2|Fv|-2.