ALGEBRAIC COMBINATORICS

no. 5
Connectivity of generating graphs of nilpotent groups
Harper, Scott1; Lucchini, Andrea2
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
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:
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
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  - 
%0 Journal Article
%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 | 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, 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

Cited by Sources: