Distance in cayley graphs on permutation groups generated by k m-Cycles

‎‎In this paper‎, ‎we extend upon the results of B‎. ‎Suceav{\u{a}} and R‎. ‎Stong [Amer‎. ‎Math‎. ‎Monthly‎, ‎۱۱۰ (۲۰۰۳) ۱۶۲--۱۶۲]‎, ‎which they computed the minimum number of ۳-cycles needed to generate an even permutation‎. ‎Let \Omega^n_{k,m} be the set of all permutations of the form c_۱ c_۲ \cdots c_k‎ ‎where c_i's are arbitrary m-cycles in S_n‎. ‎Suppose that \Gamma^n_{k,m} be the Cayley graph on subgroup of S_n generated by all permutations‎ ‎in \Omega^n_{k,m}‎. ‎We find a shortest path joining identity and any vertex of \Gamma^n_{k,m}‎, ‎for arbitrary natural number k‎, ‎and m=۲‎ , ‎\‎, ‎۳,\‎, ‎۴‎. ‎Also‎, ‎we calculate the diameter of these Cayley graphs‎. ‎As an application‎, ‎we present an algorithm for finding a short expression of a permutation as products of given permutations‎. ‎

کلیدواژه ها:

permutation group ، Cayley graph ، Quadruple cycles ، Diameter ، Expressions of permutations