The power graph yet again

Five years ago, I posted a short update on the power graph of a group. Now, finally, the paper resulting from this has appeared on the arXiv; my coauthors are Ghodratollah Aalipour, Saieed Akbari, Reza Nikandish and Farzad Shaveisi.

I don’t intend to describe all the content of this 22-page preprint here. I will mainly just draw attention to a new construction which we introduce in the paper, and highlight some of the things we don’t know about it.

The power graph

The power graph of a group has vertex set the group, with an edge between two elements if one is a power of the other. (It is by nature a directed graph, indeed it is a partial preorder, with x ≤ y if x is a power of y; but the undirected power graph determines the directed power graph up to isomorphism.)

One of our results is that the clique number of the power graph of any group is at most countably infinite. Is the same true for the chromatic number? We can only prove this in special cases (free groups, periodic groups, abelian groups).

The commuting graph

A much more studied object is the commuting graph, in which two elements are joined if and only if they commute. In this graph, central elements are joined to all other vertices, and it is customary (when asking questions about the connectedness or diameter) to delete these elements. Indeed, with this convention, Michael Giudici and Chris Parker refuted a conjecture of Jafarzadeh and Iranmanesh by showing that the diameter of the commuting graph of a finite group is unbounded, although earlier Morgan and Parker had proved that the diameter is at most 10 if the group has trivial centre. I reported on these developments here.

But, for what follows, I need to change the convention so that the centre is included. Now it is clear that the power graph is a spanning subgraph of the commuting graph: if x is a power of y then certainly x and y commute.

The new object

We define a new graph called the enhanced power graph. In this graph, again the vertex set is G: two vertices x and y are joined if they are both powers of some element z.

The power graph and commuting graph have the property that, if H is a subgroup of G, then the graph associated to H is an induced subgraph of that associated with G. The implicit existential quantifier in the definition of the extended power graph makes it not obvious that it shares that property; this can be seen by reformulating it: x and y are joined in the enhanced power graph if the group they generate is cyclic.

A clique in the enhanced power graph of a group is a cyclic or locally cyclic subgroup, and hence is at most countable. Again, we don’t know whether the chromatic number of the enhanced power graph is at most countable.

Comparisons

It is clear that the enhanced power graph lies between the power graph and the commuting graph. In the paper, we tackle, and solve (more or less), the question of when two of these graphs can be equal in a finite group.

The argument turns on looking at the direct product of two cyclic groups of prime order. In Cp×Cp, the generators of the two factors are joined in the commuting graph but not in the enhanced power graph; so if these two graphs are equal for a group G, then G cannot contain such a subgroup, and hence its Sylow subgroups are cyclic or generalised quaternion, which leads to the required characterisation.

On the other hand, if p and q are distinct primes, then in the group Cp×Cq, the generators of the factors are joined in the enhanced power graph but not in the power graph; so if these two graphs are equal, then elements of distinct prime order can never commute, so that the prime graph of the group is a null graph. Then a classification of groups with disconnected prime graph (due to Gruenberg and Kegel) can be invoked unless the group G is a p-group for some prime p.

These results assume that the group is finite. Can anything positive be said for infinite groups? (We give a classification of soluble groups with power graph equal to commuting graph without assuming finiteness.) Another open question for infinite groups is when the power graph or enhanced power graph is equal to the commuting graph after deleting central elements.

Three problems

Thus, for most groups G, these three graphs form a strict hierarchy. But what properties do differences between the graphs have? For example, for which groups G is it the case that the edges of the commuting graph not in the enhanced power graph form a connected graph (when central elements are deleted)? For which groups do the edges of the enhanced power graph not in the power graph form a connected graph?

On another subject, if a group has finite exponent, then the chromatic number of its power graph is finite; but the proof uses the Axiom of Choice. Is there a model of ZF set theory in which the power graph of an abelian group of exponent 3 cannot be coloured with three colours? (The existence of such a colouring requires us to choose one of each inverse pair of elements of such a group.)

And finally, we prove in the paper that, if three elements of a group have the property that any two generate a cyclic group, then the group generated by all three is cyclic. It seemed to us that this should already be known; but we were unable to find a reference. Does anyone know of one?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , , , . Bookmark the permalink.

2 Responses to The power graph yet again

  1. Jon Awbrey says:

    In the enhanced power graph, why not look at the triadic relation of x, y, z?

    • If we have the directed power graph, then x and y are joined in the enhanced power graph if and only if either they are connected in one direction or other or some vertex z dominates both in the power graph.
      I don’t know whether the power graph can be reconstructed from the enhanced power graph, or whether the ternary relation is really necessary — one of several open problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s