no. 5
Forbidden subgraphs in generating graphs of finite groups
Lucchini, Andrea1 ; Nemmi, Daniele1
1 Dipartimento di Matematica “Tullio Levi-Civita” Università degli Studi di Padova 35121 Padova Italy
Algebraic Combinatorics, Tome 5 (2022) no. 5, pp. 925-946.

Let G be a 2-generated finite group. The generating graph Γ(G) 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 Γ(G), with particular emphasis on those properties that can be formulated in terms of forbidden induced subgraphs. In particular we investigate when the generating graph Γ(G) 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 Γ(S n ) and Γ(A n ) are perfect if and only if n≤4). Finally we prove that for a finite group G, the properties that Γ(G) is split, chordal or C 4 -free are equivalent.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.229
Classification : 20D60, 05C25
Mots clés : 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 
@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 = {http://www.numdam.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
SP  - 925
EP  - 946
VL  - 5
IS  - 5
PB  - The Combinatorics Consortium
UR  - http://www.numdam.org/articles/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 http://www.numdam.org/articles/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, Tome 5 (2022) no. 5, pp. 925-946. doi : 10.5802/alco.229. http://www.numdam.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. Split graphs, 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

Cité par Sources :