| The star graphs is a good cayley graph, it has good point edge symmetry, layered structure, fault-tolerant performance, Hamiltonian laceability and embedding laceability. However, with the restriction on the number of vertices:n!, there is a large gap between n! and (n+1)! For expanding an an to an Sn+1. To relax the restriction of the numbers of vertices n! in an Sn, a generalized version of the star graph, the (n, k)-star graphs was proposed. An Sn,k preserves many attractive properties of an Sn such as vertex symmetry, maximal fault tolerance, simple shortest routing and hierarchical structure. So it is important to study the network structure of Sn,k. After a careful study of the basic routing algorithm of Sn and Sn,k, in this paper, we try to construct shortest paths between two different nodes in Sn,k. And we got a good result. Then, we have constructed the Merge-Delete algorithm of Sn,k.In the recent years, rings embedding in (n, k)-star graphs is paid close attention by researchers. In this paper we presents the ideas of cycle embedding in star graphs with conditional edge faults to solve the same problems in (n, k)-star graphs.In this paper, the background knowledge, current state of research and the topology structure characteristics of star graphs and (n,k)-star graphs network are studied.1. When the addresses of the origin node and the destination node of Sn k have the same1st dimension. An algorithm for constructing the routing of a message on Sn,k is proposed. We have constructed the Merge-Delete algorithm. Then, the length of paths are given and proved. It’s a good algorithm, and we could find it is convenient in the example. When the addresses of the origin node and the destination node of Sn,k have different1st dimension, using the Merge-Delete algorithm, we can construct all the shortest paths form the origin node to the destination node fast. 2. When there are conditional edge faults in(n,k)-star graphs,we construct cycles in Sn,n-2without edge faults.Firstly,the automorphism is introduced.Then,we prove that, there are all the cycles of length from7to11in S4.2without edge faults.Secondly,the mathematical induction is introduced.And we suppose that,there cycles of length from7to (？)in Sn-1,n-3,when|f|=1.Then,we prove that,there cycles of length from7to nN-1in Sn,n-2,when|f|=1. |
