A birthday discovery

Some of the standout results about graphs on groups are characterisations of the groups G for which two types of graph (for example, the power graph and the commuting graph) coincide on G.

Sometimes the proofs are long and difficult, sometimes short and elegant. I have found an example of the latter in the last couple of days, and what better birthday treat than telling you about it?

As usual, these structures have as vertex set a group G. The power digraph has an arc from x to y if y is a power of x, while the endomorphism digraph has an arc if G has an endomorphism mapping x to y. The undirected power graph and endomorphism graph are obtained from these by ignoring directions of arcs and replacing double edges (coming from two oppositely-directed arcs) by single edges.

Theorem The following are equivalent for a finite group G:

• the power digraph and endomorphism digraph on G coincide;
• the power graph and endomorphism graph on G coincide;
• G is a cyclic group.

I will take you through the proof, which is quite short. Clearly the first condition implies the second; we have to prove that the second implies the first and the third is equivalent to both the other two.

First, if G is cyclic, then any endomorphism of G is a power map. (If f maps a generator a to a^m, then it maps every element to its mth power.) So the two types of digraph (or graph) coincide on G.

Next, suppose that the power digraph and endomorphism digraph coincide. Let H be any subgroup of G. If x∈H, then all powers of x lie in H, in other words, all out-neighbours of x in the power digraph are in H. So, by our assumption, any endomorphism of G maps H into itself. Applying this to the inner automorphisms, we see that H is a normal subgroup. Thus G is a Dedekind group (every subgroup normal). From the structure of these groups, either G is nonabelian, or it has the quaternion group Q₈ as a direct factor. But the quaternion group has an automorphism permuting the three subgroups of order 4. So G is abelian. If it is not cyclic, it contains a subgroup C_p×C_p for some prime p, and it has endomorphisms mapping it onto both direct factors, a contradiction. So G is cyclic.

Finally, suppose that the power graph and endomorphism graph coincide, and let x and y be joined in this graph. I show that either there is a double arc between these vertices in both digraphs, or there is a single arc in the same direction.

Suppose first that there is an arc from x to y in the power digraph but not in the reverse direction. Then y is a power of x but not conversely, so y has smaller order than x. But then no endomorphism can map y to x. Since they are joined in the endomorphism digraph, it must be by an arc from x to y.

Finally suppose there are arcs in both directions in the power digraph. Then x and y generate the same cyclic subgroup H of G, so an endomorphism mapping x to y induces an automorphism of H, and some power of it maps y back to x. So there are arcs in both directions in the endomorphism digraph.

So there it is. I got a lot of pleasure from finding that, and I hope you had some pleasure from reading it.