Forbidden subgraphs in generating graphs of finite groups

2021/04/22 by Andrea Lucchini, Lucchini, Andrea, Daniele Nemmi +1
Computer Science · Mathematics · #Advanced Graph Theory Research #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2104.10867

openalex publication_date 2021/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a 2-generated group. The generating graph Γ(G) is the graph whose vertices are the elements of G and where two vertices g₁ and g₂ are adjacent if G = ⟨ g₁, g₂ ⟩. 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 the others, 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₄-free are equivalent.

Related

• Connectivity of generating graphs of nilpotent groups
• On power graphs of finite groups with forbidden induced subgraphs
• The generating graph of a profinite group
• Forbidden subgraphs in enhanced power graphs of finite groups
• Forbidden subgraphs on conjugacy class graphs of groups