An algorithm for finding minimal generating sets of finite groups

Document Type : Research Paper

Authors

Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand

Abstract

In this article, we study connections between components of the Cayley graph Cay(G,A), where A is an arbitrary subset of a group G, and cosets of the subgroup of G generated by A. In particular, we show how to construct generating sets of G if Cay(G,A) has finitely many components. Furthermore, we provide an algorithm for finding minimal generating sets of finite groups using their Cayley graphs.

Keywords

References

[1] V. Arvind and J. Toran, The complexity of quasigroup isomorphism and the minimum generating set problem, Algorithms and computation, Lecture Notes in Computer Science, Springer, Berlin, 4288 (2006) 233-242.
[2] P. J. Cameron, A. Lucchini, and C. M. Roney-Dougal, Generating sets of finite groups, Trans. Amer. Math. Soc., 370 No. 9 (2018) 6751-6770.
[3] X. G. Fang, C. E. Praeger, and J. Wang, On the automorphism groups of Cayley graphs of finite simple groups, J. London Math. Soc., 66 No. 3 (2002) 563-578.
[4] C. D. Godsil, Connectivity of minimal Cayley graphs, Arch. Math. (Basel), 37 No. 5 (1981) 473-476.
[5] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.10.0, 018, http://www.gap-system.org.
[6] L. Halbeisen, M. Hamilton, and P. Rozicka, Minimal generating sets of groups, rings, and _elds, Quaest. Math., 30 No. 3 (2007) 355-363.
[7] A. V. Kelarev, Labelled Cayley graphs and minimal automata, Australas. J. Combin., 30 (2004) 95-101.
[8] A. V. Kelarev, On Cayley graphs of inverse semigroups, Semigr. Forum, 72 No. 3 (2006) 411-418.
[9] A. V. Kelarev and C. E. Praeger, On transitive Cayley graphs of groups and semigroups, European J. Combin., 24 (2003) 59-72.
[10] A. V. Kelarev and S. J. Quinn, A combinatorial property and Cayley graphs of semigroups, Semigr. Forum, 66 (2003) 89-96.
[11] A. V. Kelarev, J. Ryan, and J. Yearwood, Cayley graphs as classifiers for data mining: The inuence of asymmetries, Discrete Math., 309 No. 17 (2009) 5360-5369.
[12] B. Khosravi and M. Mahmoudi, On Cayley graphs of rectangular groups, Discrete Math., 310 No. 4 (2010) 804-811.
[13] W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin., 14 (2007) Article R45, 12 pages.
[14] E. Konstantinova, Some problems on Cayley graphs, Linear Algebra Appl., 429 No. 11-12 (2008) 2754-2769.
[15] J. S. Leon, On an algorithm for finding a base and a strong generating set for a group given by generating permutations, Math. Comp., 35 No. 151 (1980) 941-974.
[16] C. H. Li, On isomorphisms of finite Cayley graphs-a survey, Discrete Math., 256 No. 1-2 (2002) 301-334.
[17] Z.-P. Lu and M.-Y. Xu, On the normality of Cayley graphs of order pq, Australas. J. Combin., 27 (2003) 81-93.
[18] A. Lucchini, The largest size of a minimal generating set of a finite group, Arch. Math. (Basel), 101 (2013) 1-8.
[19] A. Lucchini and F. Menegazzo, Computing a set of generators of minimal cardinality in a solvable group, J. Symbolic Comput., 17 No. 5 (1994) 409-420.
[20] F. Menegazzo, The number of generators of a finite group, Proceedings of the All Ireland Algebra Days, 2001 (Belfast), No. 50 (2003) 117-128.
[21] S. Panma, U. Knauer, and Sr. Arworn, On transitive Cayley graphs of strong semilattices of right (left) groups, Discrete Math., 309 No. 17 (2009) 5393-5403.
[22] J. Siagiova and J. Siran, Approaching the Moore bound for diameter two by Cayley graphs, J. Combin. Theory Ser. B, 102 No. 2 (2012) 470-473.
[23] W. Xiao and B. Parhami, Cayley graphs as models of deterministic small-world networks, Inform. Process. Lett., 97 No. 3 (2006) 115-117. 
Algebraic Structures and Their Applications
Volume 8, Issue 2
August 2021
Pages 131-143

Files

Share

How to cite

Statistics