Maximal cocliques in the generating graphs of the alternating and symmetric groups

Veronica Kelsey*, Colva Mary Roney-Dougal

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)


The generating graph Γ (G) of a finite group G has vertex set the non-identity elements of G, with two elements adjacent 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 Sn and An are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal in the case of G = An and Sn, when n is prime and n ≠ qd-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.
Original languageEnglish
Article number56879
Number of pages20
JournalCombinatorial Theory
Issue number1
Publication statusPublished - 30 Mar 2022


  • Generating graph
  • Alternating groups
  • Symmetric groups


Dive into the research topics of 'Maximal cocliques in the generating graphs of the alternating and symmetric groups'. Together they form a unique fingerprint.

Cite this