Graphs defined on algebras

Next February, I will be speaking at AAA108 (Arbeitstagung Allgemeine Algebra) in Vienna. I thought this might be a chance to take some of the work about graphs defined on groups, and see whether it can be extended to arbitrary algebras. It turns out that a surprising amount of it can.

An algebra, in this sense, is a set with a collection of operations on it; so it includes our favourites, groups, rings and fields, but is much much more general, which led me to expect that there would be little to say. Indeed, I do not see how group-theoretic constructions like the nilpotence or Engel graphs can be extended to arbitary algebras. But there are some things which work in general.

So here are some graphs defined on groups. I have written them in a way which makes it clear that they generalise: ⟨S⟩ is the subalgebra generated by a subset S, the smallest subalgebra containing S (and closed under all the operations). In this portmanteau definition, I give the rules for joining elements x and y of a group or algebra.

• The power graph: x∈⟨y⟩ or y∈⟨x⟩.
• The enhanced power graph: there exists z such that x,y∈⟨z⟩.
• The generating graph: ⟨x,y⟩ is the whole group or algebra.
• The independence graph: no minimal generating set for the group or algebra contains both x and y.
• The rank graph: no generating set of minimum cardinality contains both x and y.

I will state three theorems, concerning the first two of these graphs. First I need to define several classes of graphs:

• Perfect graphs do not contain cycles of odd length greater than 3 or their complements as induced subgraphs.
• Chordal graphs do not contain cycles of length greater than 3 as induced subgraphs.
• Cographs do not contain the 4-vertex path as an induced subgraph.

Each of these classes has a rich structure theory, but I will not discuss that here.

Now here are the three theorems for graphs on groups.

• The power graph is a perfect graph.
• If the enhanced power graph is a cograph, then it is also a chordal graph.
• (Note that the power graph is a spanning subgraph of the enhanced power graph.) The power graph and enhanced power graph are equal if and only if the group is an EPPO group: this means that all its elements have prime power order. Such groups were determined by Rolf Brandl in 1981, following earlier results by Graham Higman and Michio Suzuki.

The second of these theorems is a very recent result of Daniela Bubboloni, Francesco Fumigalli and Cheryl Praeger, in a very nice paper which I encourage you to look at: it is on the arXiv 2510.18073, where it is the first main theorem of the paper.

Somewhat to my surprise, both of the first two results are valid for completely general algebras. Here are the proofs.

For the first one, we define the directed power graph, which has an arc from x to y if and only if y∈⟨x⟩. If, as the definition suggests, we add a loop at every vertex, this is a partial preorder, that is, it is reflexive and transitive. Now the comparability graph of any partial preorder is perfect (a slight extension of a theorem of Mirsky).

For the second, the proof by Bubboloni et al. works almost unchanged. Suppose that Γ is the enhanced power graph of an algebra A and is a cograph but not a chordal graph. Then Γ contains an induced cycle. It cannot have length greater than 4, since such cycles contain 4-vertex paths. So it is a 4-cycle (a,b,c,d). Since a and b are joined, there is a vertex u such that a,b∈⟨u⟩; we choose u so that, subject to this, the subalgebra it generates is maximal.

Suppose that u is joined to c. Then there is an element v such that c and u (and hence a and b) are contained in ⟨v⟩. By the maximality of u, we must have ⟨v⟩ = ⟨u⟩, and so a is joined to c, which is false since the cycle is induced.

By an almost identical argument, u is not joined to d. But it is joined to a and b. So (u,b,c,d) is a 4-vertex path, contradicting the fact that Γ is a cograph.

What about the third theorem? The first part of the argument works in general. If the power graph of A is equal to the enhanced power graph, then in any 1-generator subalgebra of A, the 1-generator subalgebras are totally ordered by inclusion. (The proof is an exercise.) Now the cyclic subgroups of a cylic group are totally ordered by inclusion if and only if the group has prime power order.

So that leaves us to worry about the question: Is there any variety of algebras apart from groups in which the algebras satisfying the condition that the 1-generator subalgebras of a 1-generator algebra are totally ordered by inclusion?

There are some results involving the other graphs in my list which extend to arbitrary algebras; in some cases these lead to questions about when equality holds for the relevant classes of algebras, which have been answered for groups but are open in general.

Plenty to do here!