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

Abstract: The generating graph

G a m m a (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 a m m a (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 a m m a (G)

, but this coclique need not be maximal. In this paper we determine when the intransitive maximal subgroups of

e x t r m S_{n}

and

e x t r m A_{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 = e x t r m A_{n}

and

e x t r m S_{n}

, when n is prime and

n e q f r a c (q^{d} - 1) (q - 1)

for all prime powers

q

and

d g e q 2

. Namely, we show that two elements of

G

have identical sets of neighbours in

G a m m a (G)

if and only if they belong to exactly the same maximal subgroups.

This page was built for publication: Maximal Cocliques in the Generating Graphs of the Alternating and Symmetric Groups