Connectivity of generating graphs of nilpotent groups

Harper, Scott; Lucchini, Andrea

Algebraic Combinatorics, Tome 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=\langle g,h\rangle$. 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 $\left|G\right|⩾3$, also Hamiltonian. We pose several questions.

Classification : 20F05, 20D15, 05C25
Mots clés : Generating graph, connectivity, nilpotent groups.

[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