Forbidden subgraphs in generating graphs of finite groups

DOI10.5802/ALCO.229arXiv2104.10867MaRDI QIDQ6365865

Daniele Nemmi, Andrea Lucchini

Publication date: 22 April 2021

Abstract: Let $G$ be a $2$-generated group. The generating graph $Gamma(G)$ is the graph whose vertices are the elements of $G$ and where two vertices $g_1$ and $g_2$ are adjacent if $G=langle{g}_1,g_{2}angle.$ 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(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 $Gamma(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 the others, that $Gamma(S_n)$ and $Gamma(A_n)$ are perfect if and only if $nleq4$). Finally we prove that for a finite group $G$, the properties that $Gamma(G)$ is split, chordal or $C_4$-free are equivalent.

Mathematics Subject Classification ID

Arithmetic and combinatorial problems involving abstract finite groups (20D60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

This page was built for publication: Forbidden subgraphs in generating graphs of finite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365865)