# 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:
Accepted:
Published online:
DOI: 10.5802/alco.132
Classification: 20F05, 20D15, 05C25
Keywords: Generating graph, connectivity, nilpotent groups.
Harper, Scott 1; Lucchini, Andrea 2

1 School of Mathematics, University of Bristol, Bristol BS8 1UG, UK, and Heilbronn Institute for Mathematical Research, Bristol, UK.
2 Dipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, 35121 Padova, Italy
@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
AU  - Harper, Scott
AU  - Lucchini, Andrea
TI  - Connectivity of generating graphs of nilpotent groups
JO  - Algebraic Combinatorics
PY  - 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  - 
%0 Journal Article
%A Harper, Scott
%A Lucchini, Andrea
%T Connectivity of generating graphs of nilpotent groups
%J Algebraic Combinatorics
%D 2020
%P 1183-1195
%V 3
%N 5
%I MathOA foundation
%U https://doi.org/10.5802/alco.132
%R 10.5802/alco.132
%G en
%F 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/articles/10.5802/alco.132/

[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 | DOI | MR | Zbl

[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 | DOI | MR

[3] Burness, Timothy C.; Guest, Simon On the uniform spread of almost simple linear groups, Nagoya Math. J., Volume 209 (2013), pp. 35-109 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[6] Crestani, Eleonora; Lucchini, Andrea The generating graph of finite soluble groups, Israel J. Math., Volume 198 (2013) no. 1, pp. 63-74 | DOI | MR | Zbl

[7] Dirac, Gabriel Andrew Some theorems on abstract graphs, Proc. London Math. Soc. (3), Volume 2 (1952), pp. 69-81 | DOI | MR

[8] Gravier, Sylvain Hamiltonicity of the cross product of two Hamiltonian graphs, Discrete Math., Volume 170 (1997) no. 1-3, pp. 253-257 | DOI | MR | Zbl

[9] Guralnick, Robert M.; Kantor, William M. Probabilistic generation of finite simple groups, J. Algebra, Volume 234 (2000) no. 2, pp. 743-792 | DOI | MR | Zbl

[10] Harper, Scott On the uniform spread of almost simple symplectic and orthogonal groups, J. Algebra, Volume 490 (2017), pp. 330-371 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[12] Lang, Serge Algebra, Graduate Texts in Mathematics, 211, Springer-Verlag, New York, 2002, xvi+914 pages | DOI | MR | Zbl

[13] Lucchini, Andrea The diameter of the generating graph of a finite soluble group, J. Algebra, Volume 492 (2017), pp. 28-43 | DOI | MR | Zbl

[14] Lucchini, Andrea; Maróti, Attila On finite simple groups and Kneser graphs, J. Algebraic Combin., Volume 30 (2009) no. 4, pp. 549-566 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[17] Whitney, Hassler Congruent Graphs and the Connectivity of Graphs, Amer. J. Math., Volume 54 (1932) no. 1, pp. 150-168 | DOI | MR | Zbl

Cited by Sources: