Home Online Mathematical Communication Peter Cameron's Blog Graphs defined on groups

Graphs defined on groups

Peter Cameron's Blog 2021-01-23

I’ve been spending time I can ill afford on various questions related to graphs whose vertex set is a group G and which capture some of the structure of G. (I interpret this to mean that the graph is invariant under the automorphism group of G, so I don’t include Cayley graphs; anyway, so much has been said about Cayley graphs that I have little to add.) My notes on this are up to 44 pages already. So I will give a brief summary here. If you are interested in working on this, and would like a copy of the notes, let me know.

The group G will here be finite; that already leads to interesting questions. The graphs I consider are (with the joining rule for vertices x and y):

  • the power graph, one of x and y is a power of the other;
  • the enhanced power graph, x and y are both powers of an element z (equivalently, ⟨x,y⟩ is cyclic);
  • the deep commuting graph, the preimages of x and y commute in every central extension of G;
  • the commuting graph, xy = yx (equivalently, ⟨x,y⟩ is abelian);
  • the non-generating graph, ⟨x,y⟩ is a proper subgroup of G.

These form a hierarchy: the edge set of each graph is contained in that of the next, except possibly the last which is a bit of an outlier, but contains the one before provided G is either non-abelian or not 2-generated.

Several other graphs also appear in the story:

  • the Gruenberg–Kegel graph of G, whose vertex set is the set of prime divisors of the order of G, primes p and q joined if G contains an element of order pq;
  • the intersection graph of a family C of non-trivial proper subgroups of G, where two subgroups are joined if their intersection is non-trivial.

For the graphs in the hierarchy, I also define the reduced graph to be the induced subgraph on the set of non-identity elements of G. (For each graph in the hierarchy, the identity is joined to all other vertices. Ideally we should form the reduced graph by removing all vertices which are joined to all others; the set of such vertices is explicitly known in all cases except for the non-generating graph, and in particular if the centre of G is trivial the only such vertex in all cases except possibly the non-generating graph is the identity.)

To avoid having to make special provision for the non-generating graph too often, I sometimes assume that G is non-abelian and 2-generated. This of course includes all finite simple groups.

Inclusion, equality, and differences

As said above, the power graph, enhanced power graph, deep commuting graph, commuting graph, and non-generating graph (if G is non-abelian 2-generated) form a hierarchy. So a natural question is: when can two of these be equal?

Starting at the top, if G is non-abelian and 2-generated, then the non-generating graph is equal to the commuting graph if and only if G is a minimal non-abelian group. Such groups were all determined by Miller and Moreno in 1904.

The commuting graph is equal to the enhanced power graph if and only if G contains no subgroup Cp×Cq for distinct primes p and q. This is equivalent to saying that the Gruenberg–Kegel graph of G is a null graph.

The enhanced power graph is equal to the power graph if and only if G contains no subgroup Cp×Cp for any prime p. This is equivalent to saying that the Sylow subgroups of G are all cyclic or (if p = 2) generalized quaternion.

The groups in these two results can be determined more or less explicitly. So in particular one can determine the groups whose power graph and commuting graph are equal.

The deep commuting graph is a bit more difficult, but there are criteria for it to be equal to either the commuting graph of the enhanced power graph. Equality of the deep commuting graph and commuting graph holds if and only if the Schur multiplier and the Bogomolov multiplier of G are equal. (I won’t define either of these here; there are references in the notes.)

Given these results it is natural to ask what can be said about the differences. For the “non-commuting, non-generating graph”, Saul Freedman has good results, which will be in his thesis; analysis of the question of connectedness for nilpotent groups is in a paper shortly to appear in the Electronic Journal of Combinatorics.

For most other pairs, very little is known. I have started thinking about the “commuting, non-power graph”, but I can’t say much as yet.

Induced subgraphs

I have discussed this in a rather fragmented way on the blog before, so here is a summary. For each type T of graph in the hierarchy except the power graph, these graphs on finite groups are universal: for every finite graph Γ there is a group such that Γ is an induced subgraph of T(G). Though the results are uniform, the proof techniques are rather different for the different types.

This still leaves an interesting question or two: bound the order of G in terms of &GAmma;; and how large does a group have to be for T(G) to embed all n-vertex graphs?

For the power graph, the situation is a little different. The power graph of any finite group is the comparability graph of a partial order; but any finite graph which is the comparability graph of a partial order is an induced subgraph of the power graph of some finite group. Similar further questions can be asked.

Cographs and twin reduction

A small digression into graph theory here.

Two vertices u,v of a graph are called twins if they have the same neighbours, apart possibly from one another. I will distinguish open twins (equal open neighbourhoods) and closed twins (equal closed neighbourhoods) where necessary. Being equal or twins is an equivalence relation on the vertex set. (No vertex can have both an open twin and a closed twin.)

If two vertices are twins in a graph, we can identify them. This process can be continued until no more pairs of twins remain. The result is unique, independent of the order of reduction. I will call this graph the cokernel of the original graph.

Another description is that two vertices are twins if and only if the transposition interchanging them and fixing all other vertices is an automorphism of a graph. So the automorphism group of the graph has a normal subgroup which is the direct product of symmetric groups on the twin classes.

A cograph is a graph which has no induced subgraph isomorphic to the 4-vertex path P4. The class of cographs is the smallest class of graphs containing the trivial vertex and closed under complement and disjoint union. Any cograph on more than one vertex contains a pair of twins; indeed, a graph is a cograph if and only if its cokernel has just one vertex.

From this it can be shown that the automorphism groups of cographs can be obtained from the trivial group by the two operations “direct product” and “wreath product with a symmetric group”.

Forbidden subgraphs

Various important classes of graphs (such as perfect graphs, cographs, chordal graphs, threshold graphs, and split graphs) can be defined by a list of forbidden induced subgraphs (as we saw above for cographs).

For each such class, and each type T of graph in the hierarchy, we can ask: for which groups G is T(G) in the prescribed graph class? There are results for some cases, but our knowledge is not complete.

A particularly interesting case: For which groups is it true that the power graph is a cograph? Curiously, there is a necessary condition, and a sufficient condition, for this purely in terms of the Gruenberg–Kegel graph; but there is no necessary and sufficient condition in these terms. (The groups PSL(2,11) and M11 have the same GK graph; but the power graph of the first, but not that of the second, is a cograph.

Furthermore, the innocent-looking question “For which prime powers q is PSL(2,q) a cograph?” leads into fairly deep number-theoretic waters; I do not expect a solution any time soon.

I have computed the cokernels of all graphs in the hierarchy for non-abelian fin ite simple groups with orders up to that of M11; there is a ta ble of their numbers of vertices in the notes.

Connectedness

The question of connectedness of some of the graphs in the hierarchy has been well studied. Of course, the question for the various “difference” graphs is much less well studied.

Here is a result which may be of some interest as tying things together. For a finite group G with Z(G) =&nsbp;1, the following are equivalent:

  • the Gruenberg–Kegel graph of G is connected;
  • the reduced commuting graph of G is connected;
  • the intersection graph of non-trivial abelian subgroups of G is connected;
  • the intersection graph of maximal abelian subgroups of G is connected.

Automorphism groups

If G is a non-trivial finite group, then the twin relation on T(G) is non-trivial for any type T in the hierarchy. If g is an element of order greater than 2, then any element h generating the same cyclic subgroup is a twin of g. If no such element exists, then G is elementary abelian, and the result is easily checked directly (type by type).

So the automorphism group of T(G) contains the automorphism group of G, and also the direct product of symmetric groups on the twin classes. But there may be more, and the picture is not entirely clear. In particular, the reduction process can introduce extra automorphisms.

An interesting example of this was found by Colva Roney-Dougal. Take G to be the group PSL(2,16). The automorphism group of its non-generating graph separates the sets of elements of orders 3 and 5. But after twin reduction, these two classes can be interchanged! The automorphism group of the cokernel of this graph is C2×PΓL(2,16).

The nicest possible situation is exemplified by M11. The cokernel of the power graph has 1212 vertices and automorphism group M11.

But of course, if (say) the power graph of G is a cograph, then its automorphism group is built from the trivial group by direct product and wreath product with symmetric groups, and does not reflect the structure of G very well.

More

There is more to say, both about these graphs and about others that can be defined, but that is enough for now.