Document Type : Research Paper

**Authors**

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

10.29252/as.2021.2029

**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**

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

Summer and Autumn 2021

Pages 131-143