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

Document Type : Research Paper


Iran University of Science and Technology


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


Main Subjects

[1] S. Annin and S. Maglione, Economical generating sets for the symmetric and alternating groups consisting of cycles of a xed length, J. Algebra Appl., 11 no. 16 (2012) pp.8.
[2] L. Babai and A. Seress, On the diameter of Cayley graphs of the symmetric group, J. Combin. Theory Ser. A, 49 no. 1 (1988) 175-179.
[3] L. Babai and A. Seress, On the diameter of p ermutation groups, European J. Combin., 13 no. 4 (1992) 231-243.
[4] M. Camelo, D. Papadimitriou, L. Fbrega and P. Vil, Efficient routing in data center with underlying Cayley graph, In: Complex Networks V, (Springer), 549 (2014) 189-197.
[5] G. Co op erman and L. Finkelstein, A strong generating test and short presentations for p ermutation groups, J. Symbolic Comput., 12 no. 4-5 (1991) 475-497.
[6] A. Kalka, M. Teicher and B. Tsaban, Short expressions of p ermutations as pro ducts and cryptanalysis of the algebraic eraser, Adv. Appl. Math., 49 no. 1 (2012) 57-76.
[7] E. Konstantinova, On reconstruction of signed p ermutations distorted by reversal errors, Discrete Math., 308 no. 5-6 (2008) 974-984.
[8] E. Konstantinova, Vertex reconstruction in Cayley graphs, Discrete Math., 309 no. 3 (2009) 548-559.
[9] V. Levenshtein and J. Siemons, Error graphs and the reconstruction of elements in groups, J. Combin. Theory Ser. A, 116 no. 4 (2009) 795-815.
[10] T. Minkwitz, An algorithm for solving the factorization problem in p ermutation groups, J. Symbolic Comput., 26 no. 1 (1998) 89-95.
[11] T. Phongpattanacharo en and J. Siemons, Metric intersection problems in Cayley graphs and the Stirling recursion, Aequationes Math., 85 no. 3 (2013) 387-408.
[12] J. L. Soncco- Alvarez, G. M. Almeida, J. Becker and M. Ayala-Rincon, Parallelization of genetic algorithms for sorting p ermutations by reversals over biological data, Int. J. Hybrid Intel l. Syst., 12 no. 1 (2015) 53-64.
[13] B. Suceava and R. Stong, The fewest 3-cycles to generate an even p ermutation, Amer. Math. Monthly, 110 no. 2 (2003) 162-162.
Volume 6, Issue 3 - Serial Number 3
September 2017
Pages 45-59
  • Receive Date: 11 December 2016
  • Revise Date: 06 April 2017
  • Accept Date: 08 April 2017
  • Published Online: 01 September 2017