# ALGEBRAIC COMBINATORICS

Forbidden subgraphs in generating graphs of finite groups
Algebraic Combinatorics, Volume 5 (2022) no. 5, pp. 925-946.

Let $G$ be a $2$-generated finite group. The generating graph $\Gamma \left(G\right)$ is the graph whose vertices are the elements of $G$ and where two vertices ${g}_{1}$ and ${g}_{2}$ are adjacent if $G=〈{g}_{1},{g}_{2}〉.$ This graph encodes the combinatorial structure of the distribution of generating pairs across $G.$ In this paper we study some graph theoretic properties of $\Gamma \left(G\right)$, with particular emphasis on those properties that can be formulated in terms of forbidden induced subgraphs. In particular we investigate when the generating graph $\Gamma \left(G\right)$ is a cograph (giving a complete description when $G$ is soluble) and when it is perfect (giving a complete description when $G$ is nilpotent and proving, among other things, that $\Gamma \left({S}_{n}\right)$ and $\Gamma \left({A}_{n}\right)$ are perfect if and only if $n\le 4$). Finally we prove that for a finite group $G$, the properties that $\Gamma \left(G\right)$ is split, chordal or ${C}_{4}$-free are equivalent.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.229
Classification: 20D60,  05C25
Keywords: cographs, generating graph, perfect graphs
Lucchini, Andrea 1; Nemmi, Daniele 1

1 Dipartimento di Matematica “Tullio Levi-Civita” Università degli Studi di Padova 35121 Padova Italy
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{ALCO_2022__5_5_925_0,
author = {Lucchini, Andrea and Nemmi, Daniele},
title = {Forbidden subgraphs in generating graphs of finite groups},
journal = {Algebraic Combinatorics},
pages = {925--946},
publisher = {The Combinatorics Consortium},
volume = {5},
number = {5},
year = {2022},
doi = {10.5802/alco.229},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.229/}
}
TY  - JOUR
AU  - Lucchini, Andrea
AU  - Nemmi, Daniele
TI  - Forbidden subgraphs in generating graphs of finite groups
JO  - Algebraic Combinatorics
PY  - 2022
DA  - 2022///
SP  - 925
EP  - 946
VL  - 5
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.229/
UR  - https://doi.org/10.5802/alco.229
DO  - 10.5802/alco.229
LA  - en
ID  - ALCO_2022__5_5_925_0
ER  - 
%0 Journal Article
%A Lucchini, Andrea
%A Nemmi, Daniele
%T Forbidden subgraphs in generating graphs of finite groups
%J Algebraic Combinatorics
%D 2022
%P 925-946
%V 5
%N 5
%I The Combinatorics Consortium
%U https://doi.org/10.5802/alco.229
%R 10.5802/alco.229
%G en
%F ALCO_2022__5_5_925_0
Lucchini, Andrea; Nemmi, Daniele. Forbidden subgraphs in generating graphs of finite groups. Algebraic Combinatorics, Volume 5 (2022) no. 5, pp. 925-946. doi : 10.5802/alco.229. https://alco.centre-mersenne.org/articles/10.5802/alco.229/

[1] Bray, John N.; Holt, Derek F.; Roney-Dougal, Colva M. The maximal subgroups of the low-dimensional finite classical groups. With a foreword by Martin Liebeck, London Mathematical Society Lecture Note Series, 407, Cambridge University Press, Cambridge, 2013, xiv+438 pages | DOI

[2] 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

[3] 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

[4] Burness, Timothy C; Guralnick, Robert M; Harper, Scott The spread of a finite group, Ann. of Math., Volume 193 (2021) no. 2, pp. 619-687 | MR | Zbl

[5] Cameron, Peter J. Graphs defined on groups, Int. J. Group Theory, Volume 11 (2022) no. 2, pp. 53-107 | MR | Zbl

[6] Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin The strong perfect graph theorem, Ann. of Math. (2), Volume 164 (2006) no. 1, pp. 51-229 | DOI | MR | Zbl

[7] 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

[8] Dixon, John D.; Mortimer, Brian Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, New York, 1996, xii+346 pages | DOI | MR

[9] Foldes, Stéphane; Hammer, Peter L., Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977) (1977), p. 311-315. Congressus Numerantium, No. XIX | MR | Zbl

[10] GAP – Groups, Algorithms, and Programming, Version 4.11.1 (2021) https://www.gap-system.org

[11] Gaschütz, Wolfgang Zu einem von B. H. und H. Neumann gestellten Problem, Math. Nachr., Volume 14 (1955) no. 4-6, pp. 249-252 | DOI | MR | Zbl

[12] Gaschütz, Wolfgang Die Eulersche funktion endlicher auflösbarer gruppen, Illinois J. Math., Volume 3 (1959) no. 4, pp. 469-476 | Zbl

[13] 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

[14] Harper, Scott; Lucchini, Andrea Connectivity of generating graphs of nilpotent groups, Algebr. Combin., Volume 3 (2020) no. 5, pp. 1183-1195 | DOI | Numdam | MR | Zbl

[15] Jones, Gareth A Primitive permutation groups containing a cycle, Bull. Aust. Math. Soc., Volume 89 (2014) no. 1, pp. 159-165 | DOI | MR | Zbl

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

[17] Pierro, Emilio The Möbius function of the small Ree groups, Australas. J. Combin., Volume 66 (2016), pp. 142-176 | MR | Zbl

[18] Ravindra, G.; Parthasarathy, K. R. Perfect product graphs, Discrete Math., Volume 20 (1977/78) no. 2, pp. 177-186 | DOI | MR | Zbl

[19] Robinson, Derek J. S. A course in the theory of groups, Graduate Texts in Mathematics, 80, Springer-Verlag, New York, 1996, xviii+499 pages | DOI | MR

[20] Shen, Rulin Intersection graphs of subgroups of finite groups, Czechoslovak Math. J., Volume 60 (2010) no. 4, pp. 945-950 | DOI | MR | Zbl

Cited by Sources: