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 $\mathrm{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 $\mathrm{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