ALGEBRAIC COMBINATORICS

no. 5

Connectivity of generating graphs of nilpotent groups
Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1183-1195.

Let G be 2-generated group. The generating graph Γ(G) is the graph whose vertices are the elements of G and where two vertices g and h are adjacent if G=〈g,h〉. This graph encodes the combinatorial structure of the distribution of generating pairs across G. In this paper we study several natural graph theoretic properties related to the connectedness of Γ(G) in the case where G is a finite nilpotent group. For example, we prove that if G is nilpotent, then the graph obtained from Γ(G) by removing its isolated vertices is maximally connected and, if |G|⩾3, also Hamiltonian. We pose several questions.

Received: 2020-02-04
Revised: 2020-05-30
Accepted: 2020-06-12
Published online: 2020-10-12
DOI: https://doi.org/10.5802/alco.132
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] Breuer, Thomas; Guralnick, Robert M.; Kantor, William M. Probabilistic generation of finite simple groups, II, J. Algebra, Volume 320 (2008) no. 2, pp. 443-494 | Article | MR 2422303 | Zbl 1181.20013

[2] Breuer, Thomas; Guralnick, Robert M.; Lucchini, Andrea; Maróti, Attila; Nagy, Gábor P. 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] Burness, Timothy C.; Guest, Simon 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] Burness, Timothy C.; Harper, Scott Finite groups, 2-generation and the uniform domination number (to appear in Israel J. Math.)

[5] Burness, Timothy C.; Harper, Scott 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] Crestani, Eleonora; Lucchini, Andrea 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] Dirac, Gabriel Andrew Some theorems on abstract graphs, Proc. London Math. Soc. (3), Volume 2 (1952), pp. 69-81 | Article | MR 47308

[8] Gravier, Sylvain 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] Guralnick, Robert M.; Kantor, William M. Probabilistic generation of finite simple groups, J. Algebra, Volume 234 (2000) no. 2, pp. 743-792 | Article | MR 1800754 | Zbl 0973.20012

[10] Harper, Scott 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] Hellwig, Angelika; Volkmann, Lutz 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] Lang, Serge Algebra, Graduate Texts in Mathematics, Volume 211, Springer-Verlag, New York, 2002, xvi+914 pages | Article | MR 1878556 | Zbl 0984.00001

[13] Lucchini, Andrea 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] Lucchini, Andrea; Maróti, Attila 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] Lucchini, Andrea; Maróti, Attila 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] Wang, Wei; Yan, Zhidan 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] Whitney, Hassler Congruent Graphs and the Connectivity of Graphs, Amer. J. Math., Volume 54 (1932) no. 1, pp. 150-168 | Article | MR 1506881 | Zbl 0003.32804