Transactions on Combinatorics (Sep 2017)

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

  • Zohreh Mostaghim,
  • Mohammad Hossein Ghaffari

DOI
https://doi.org/10.22108/toc.2017.21473
Journal volume & issue
Vol. 6, no. 3
pp. 45 – 59

Abstract

Read online

‎‎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