The Path And Geodesic Pancyclic Embedding In The Hypercubes And K-ary N-cubes With Faulty Edges

It is well known that the hypercube and k-ary n-cube are popular interconnection networks. They have many good properties, such as recursive structure, symmetry, efficient routing etc. The rings and linear arrays are two of most important interconnection networks for parallel computing. Many efficient algorithms with low communication cost were originally designed based on them. Thus it is interested to give paths and cycles of various lengths in networks. One of the most central issues in various interconnection network is to find node-disjoint paths. The problem has received much attention because of its numerous applicatious in high performance communicationm networks, fault-tolerant routings, and so it. Failures are inevitable when a large computer system is put in use. Hence, it is very important to study node-disjoint path and cycle embedding in the faulty hypercube and k-ary n-cube. In this thesis, our main results are as follows.(1) Let Qn3 be a 3-ary n-cube, where n≥2, and F be any subset of edges with |F|≤2n-4. Assume that x1,x2,y1 and y2 are any four distinct vertices in Qn3. Then there exist two fault-free vertex-disjoint paths P1 between x1, and y1 and P2 between x2 and y2 such that V(P1)∪V(P2)=V(Qn).(2) Let Qn be a the n-cube, where n≥3, and F be any subset of edges with |F|≤n-3. Assume that x1,x2,y1 and y2 are any four distinct vertices in Qn such that both d(x1,y1) and d(x2,y2) are odd. Then there exist two fault-free vertex-disjoin paths P1 between xx and y1 and P2 between x, and y2 such that V(P1)∪V(P2)=V(Qn). The upper bound n-3 of number of faulty edges is tight.(3) Assume that u=(u1,u2,…,un)and v=(v1,v2,…,vn) be are any two distinct vertices in Qnk(n≥2,k≥3), where 0≤di≤k/2,(i=1,…,n), d=d1+d2+…+dn≥1 and N=kn, there exists a cycle C of every even length from 2d+2 to N such that the distance of u and v in C is d in Qnk. Moreover, if and only if 1≤i