Let be -generated group. The generating graph is the graph whose vertices are the elements of and where two vertices and are adjacent if . This graph encodes the combinatorial structure of the distribution of generating pairs across . In this paper we study several natural graph theoretic properties related to the connectedness of in the case where is a finite nilpotent group. For example, we prove that if is nilpotent, then the graph obtained from by removing its isolated vertices is maximally connected and, if , also Hamiltonian. We pose several questions.
Revised: 2020-05-30
Accepted: 2020-06-12
Published online: 2020-10-12
Classification: 20F05, 20D15, 05C25
Keywords: Generating graph, connectivity, nilpotent groups.
@article{ALCO_2020__3_5_1183_0, author = {Harper, Scott and Lucchini, Andrea}, title = {Connectivity of generating graphs of~nilpotent groups}, journal = {Algebraic Combinatorics}, pages = {1183--1195}, publisher = {MathOA foundation}, volume = {3}, number = {5}, year = {2020}, doi = {10.5802/alco.132}, language = {en}, url = {alco.centre-mersenne.org/item/ALCO_2020__3_5_1183_0/} }
Harper, Scott; Lucchini, Andrea. Connectivity of generating graphs of nilpotent groups. Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1183-1195. doi : 10.5802/alco.132. https://alco.centre-mersenne.org/item/ALCO_2020__3_5_1183_0/
[1] Probabilistic generation of finite simple groups, II, J. Algebra, Volume 320 (2008) no. 2, pp. 443-494 | Article | MR 2422303 | Zbl 1181.20013
[2] Hamiltonian cycles in the generating graphs of finite groups, Bull. Lond. Math. Soc., Volume 42 (2010) no. 4, pp. 621-633 | Article | MR 2669683
[3] On the uniform spread of almost simple linear groups, Nagoya Math. J., Volume 209 (2013), pp. 35-109 | Article | MR 3032138 | Zbl 1271.20012
[4] Finite groups, -generation and the uniform domination number (to appear in Israel J. Math.)
[5] On the uniform domination number of a finite simple group, Trans. Amer. Math. Soc., Volume 372 (2019) no. 1, pp. 545-583 | Article | MR 3968779 | Zbl 07076400
[6] The generating graph of finite soluble groups, Israel J. Math., Volume 198 (2013) no. 1, pp. 63-74 | Article | MR 3096630 | Zbl 1300.20021
[7] Some theorems on abstract graphs, Proc. London Math. Soc. (3), Volume 2 (1952), pp. 69-81 | Article | MR 47308
[8] Hamiltonicity of the cross product of two Hamiltonian graphs, Discrete Math., Volume 170 (1997) no. 1-3, pp. 253-257 | Article | MR 1452953 | Zbl 0876.05063
[9] Probabilistic generation of finite simple groups, J. Algebra, Volume 234 (2000) no. 2, pp. 743-792 | Article | MR 1800754 | Zbl 0973.20012
[10] On the uniform spread of almost simple symplectic and orthogonal groups, J. Algebra, Volume 490 (2017), pp. 330-371 | Article | MR 3690337 | Zbl 1427.20023
[11] Maximally edge-connected and vertex-connected graphs and digraphs: a survey, Discrete Math., Volume 308 (2008) no. 15, pp. 3265-3296 | Article | MR 2423410 | Zbl 1160.05038
[12] Algebra, Graduate Texts in Mathematics, Volume 211, Springer-Verlag, New York, 2002, xvi+914 pages | Article | MR 1878556 | Zbl 0984.00001
[13] The diameter of the generating graph of a finite soluble group, J. Algebra, Volume 492 (2017), pp. 28-43 | Article | MR 3709139 | Zbl 1426.20009
[14] On finite simple groups and Kneser graphs, J. Algebraic Combin., Volume 30 (2009) no. 4, pp. 549-566 | Article | MR 2563141 | Zbl 1206.20024
[15] On the clique number of the generating graph of a finite group, Proc. Amer. Math. Soc., Volume 137 (2009) no. 10, pp. 3207-3217 | Article | MR 2515391 | Zbl 1179.05052
[16] Connectivity of Kronecker products with complete multipartite graphs, Discrete Appl. Math., Volume 161 (2013) no. 10-11, pp. 1655-1659 | Article | MR 3043121 | Zbl 1286.05083
[17] Congruent Graphs and the Connectivity of Graphs, Amer. J. Math., Volume 54 (1932) no. 1, pp. 150-168 | Article | MR 1506881 | Zbl 0003.32804