Maximal Cocliques in the Generating Graphs of the Alternating and Symmetric Groups

2020/07/23 by Veronica Kelsey, Colva M. Roney‐Dougal, Kelsey, Veronica +1 · 1 citation
Mathematics · Engineering · Computer Science · #Finite Group Theory Research #graph theory and CDMA systems #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2007.12021

Abstract

The generating graph Γ(G) of a finite group G has vertex set the non-identity elements of G, with two elements connected exactly when they generate G. A coclique in a graph is an empty induced subgraph, so a coclique in Γ(G) is a subset of G such that no pair of elements generate G. A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of G form a coclique in Γ(G), but this coclique need not be maximal. In this paper we determine when the intransitive maximal subgroups of \textrmS_n and \textrmA_n are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal [3] in the case of G = \textrmA_n and \textrmS_n, when n is prime and n ≠ ((q^d -1))/((q-1)) for all prime powers q and d ≥ 2. Namely, we show that two elements of G have identical sets of neighbours in Γ(G) if and only if they belong to exactly the same maximal subgroups.

Cited by

• Coclique level structure for stochastic chemical reaction networks

Related

• Co-maximal subgroup graph characterized by forbidden subgraphs
• The invariably generating graph of the alternating and symmetric groups
• A study of the Structural Properties of finite G-graphs and their Characterisation
• Enhanced power graphs of finite groups with cograph structure
• Alternating and symmetric groups with Eulerian generating graph