Transactions on Combinatorics (Sep 2017)
Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
Abstract
In this paper, we extend upon the results of B. Suceav{u{a}} and R. Stong [Amer. Math. Monthly, 110 (2003) 162--162], which they computed the minimum number of 3-cycles needed to generate an even permutation. Let $Omega^n_{k,m}$ be the set of all permutations of the form $c_1 c_2 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=2 , , 3,, 4$. 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.
Keywords
