Mostaghim, Z., Ghaffari, M. (2017). Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles. Transactions on Combinatorics, 6(3), 45-59. doi: 10.22108/toc.2017.21473

Zohreh Mostaghim; Mohammad Hossein Ghaffari. "Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles". Transactions on Combinatorics, 6, 3, 2017, 45-59. doi: 10.22108/toc.2017.21473

Mostaghim, Z., Ghaffari, M. (2017). 'Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles', Transactions on Combinatorics, 6(3), pp. 45-59. doi: 10.22108/toc.2017.21473

Mostaghim, Z., Ghaffari, M. Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles. Transactions on Combinatorics, 2017; 6(3): 45-59. doi: 10.22108/toc.2017.21473

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

[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, Eﬃcient 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.