Digraphs on groups

I have spent a lot of time recently thinking about graphs on groups. To recall the rules: the vertex set must be the group (in general, but not here, I allow an automorphism-invariant subset or the quotient by an automorphism-invariant equivalence relation); the graph must be defined in terms of the group structure with no arbitrary choices; so the automorphism group of the group acts as automorphisms of the graph.

There are many many examples of graphs on groups. (Some examples: power graph, enhanced power graph, intersection power graph, commuting graph, deep commuting graph, generating graph, nilpotency graph, solubility graph, …).

However, I have only three examples of directed graphs defined on groups. I would be very interested to have more; let me know your thoughts.

From any directed graph we can obtain an undirected graph, by replacing single or double arcs by undirected edges.

In this post, I will describe the examples (the power digraph, endomorphism digraph, and Engel digraph), and then describe their very different behaviour in two areas (recovering the directions from the undirected graph, and universality).

The three digraphs

First, chronologically, is the power digraph, defined by Kelarev and Quinn in 2000. There is an arc x→y if y is a power of x.

Second, the endomorphism digraph: there is an arc x→y if there is an endomorphism of the group mappping x to y.See arXiv 2511.15602.

And third, the Engel digraph: there is an arc x→y if [y,x,x,…x]=1, where the left-normed iterated commutator has first element y and then, say, k elements x; I will say the pair (x,y) has depth k if this holds. (The order of the arc indicates that I think of commutation by x as an operator applied repeatedly to y. See arXiv 2408.03789.

I observe in arXiv 2602.00712 that the definitions of the first two digraphs can be extended to arbitrary algebras (in the sense of universal algebra). The third seems specific to groups.

Reconstructing directions

I explained how to get a graph from a digraph by ignoring directions. Can you go back? One of my first results on the power graph was to give the answer “yes, up to isomorphism” in the case of the power graph. Bubboloni and Pinzauti gave an algorithm for this reconstruction.

Here is a problem I have posed several times, though I don;t think I have written it down. Suppose we apply the algorithm of Bubboloni and Pinzauti to an arbitrary graph. There are three possibilities, each of which seems interesting.

• The algorithm always succeeds. Thus, it produces some kind of distinguished orientation for any graph.
• The algorithm fails if the input graph is not the power graph of a group. In this case, we have a recognition algorithm for power graphs.
• The algorithm sometimes succeeds and sometimes fails. In this case we have a potentially interesting class of graphs, those for which it succeeds, which we might call “pseudo-power graphs”.

In the case of the endomorphism graph, there are simple examples to show that reconstruction fails. For example, let p be an odd prime, and consider that two groups of order p³ and exponent p. The undirected graphs are both complete, but the directed graphs are quite different.

The Engel graphs are perhaps the most interesting. Reconstruction is not true in general, but failure is quite rare. There are only two group orders below 100 for which non-isomorphic Engel digraphs give rise to isomorphic Engel graphs, namely 54 and 96. The situation is certainly not understood!

Universality

A class of digraphs is universal if every finite digraph can be embedded as an induced sub-digraph in some digraph in the class.

Neither power digraphs nor endomorphism digraphs form universal classes; the reasons are the same in both cases. THese digraphs are transitive (as relations); that is, if x→y and y→z, then x→z.

As far as I know, the question whether they are universal for transitive digraphs (partial preorders) is still open.

Things are different for the Engel digraphs, which do indeed form a universal class. Indeed, a much stronger result is true. Above I defined the depth of a pair (x,y) to be the least k such that commuting y with x k times gives the identity; I will say the depth is infinite if you nevver get the identity.

Now consider a finite digraph with positive integers on the arcs. Can it be embedded in an Engel digraph in such a way that, if x→y is an arc with label k, then the pair (x,y) has depth k, while if there is no arc then the depth is infinite?

There is one small obstruction. Saying that (x,y) has depth 1 simply means that x commutes with y, so it implies that (y,x) also has depth 1; so given an arc with label 1, it is necessary that the converse arc also exists and has label 1.

Now our theorem says that this is the only obstruction: labelled Engel digraphs are universal for labelled digraphs satisfying this condition.

Conclusion

I mentioned a couple of problems already. Here is another.

The power digraph and endomorphism digraph are both transitive relations. I wrote earlier about the groups for which they coincide (just cyclic groups). But now one could ask: For which groups is the Engel digraph transitive? For which of these (if any) does it coincide with the power digraph, or with the endomorphism digraph?