پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,731,099 |
| تعداد دریافت فایل اصل مقاله | 17,563,143 |
Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles | ||
| Transactions on Combinatorics | ||
| مقاله 5، دوره 6، شماره 3، آذر 2017، صفحه 45-59 اصل مقاله (256.29 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2017.21473 | ||
| نویسندگان | ||
| Zohreh Mostaghim* ؛ Mohammad Hossein Ghaffari | ||
| 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. | ||
| کلیدواژهها | ||
| permutation group؛ Cayley graph؛ Quadruple cycles؛ Diameter؛ Expressions of 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, 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. | ||
|
آمار تعداد مشاهده مقاله: 1,086 تعداد دریافت فایل اصل مقاله: 784 |
||