# ALGEBRAIC COMBINATORICS

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 $\Gamma \left(G\right)$ 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 $\Gamma \left(G\right)$ in the case where $G$ is a finite nilpotent group. For example, we prove that if $G$ is nilpotent, then the graph obtained from $\Gamma \left(G\right)$ by removing its isolated vertices is maximally connected and, if $|G|⩾3$, also Hamiltonian. We pose several questions.

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},
publisher = {MathOA foundation},
volume = {3},
number = {5},
year = {2020},
pages = {1183-1195},
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