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

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 S_n and A_n are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal in the case of G = A_n and S_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.