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:
Accepted:
Published online:
Classification: 20F05, 20D15, 05C25
Keywords: Generating graph, connectivity, nilpotent groups.
Author's affiliations:
@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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.132/} }
TY - JOUR TI - Connectivity of generating graphs of nilpotent groups JO - Algebraic Combinatorics PY - 2020 DA - 2020/// SP - 1183 EP - 1195 VL - 3 IS - 5 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.132/ UR - https://doi.org/10.5802/alco.132 DO - 10.5802/alco.132 LA - en ID - ALCO_2020__3_5_1183_0 ER -
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/articles/10.5802/alco.132/
[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, 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
Cited by Sources: