Designing Of The Parallel Routing Algorithm On Star Graphs And Ring Embedding In(n,k)-star Graphs

The star graphs is a good cayley graph, it has good point edge symmetry, layered structure, fault-tolerant performance, Hamiltonian laceability and embedding laceability. So, taking the star graph as an Internet network mode is paid close attention by researchers recently. Moreover, it is significant for Internet network that data transmission from origin to destination effectively and correctly. Based on the topology structure characteristics of star graph network, a parallel paths search algorithm is designed and presented in this paper. In this paper, we construct an algorithm based on Hamiltonian circuit Latin square (HCLS) to search node-disjoint paths from any origin node to the destination node. And then, we calculate the number of node-disjoint paths and length of each path. And the conclusion is proved in the end.Sn k is an attractive alternative to the hypercube and also a generalized version of Sn. It is isomorphic to n-star graph if k=n-1, and it is isomorphic to n-complete graph when k=1. As there is a close relationship between star graphs and (n,k)-star graphs, in this paper we cite ideas of cycle embedding in star graphs with conditional edge faults, to solve the same problems in (n,k)-star graphs. We will solve this problem in two case, and prove that we can find fault-free Hamilton rings in Sn2, with|f|≤n-3, and n≥4.In addition, we cite ideas of cycle embedding in star graphs with conditional node faults, to solve the same problem in (n,k)-star graphs. Compare with the star graphs, the (n,k)-star graphs is more complicated. So, in this paper we main consider a special situation k=n-2.In addition, by applying the supper cycle, we prove there are (4,2)-super cycles of length from1to n!/4! in Sn,n-2with n≥5. Then, we will prove when f≤[n!/(2×4!)], we can find all fault free cycles of length from1to n!/2-f...