Over the summer I have had the pleasure of supervising a vacation student Aedan Pope. This is a program funded by the Australian Mathematical Sciences Institute which allows maths students to spend 6 weeks working on a project in the summer vacation (usually after third year) and also funds a trip to Sydney for the student to go to the CSIRO‘s Big Day In.

Aedan Pope’s research project focussed on commuting graphs of groups and we have just submitted a paper with the results. It is available on the arxiv. I will outline the work here.

Given a group *G*, the commuting graph of *G* is the graph whose vertices are the elements of *G *which do not lie in the centre of *G* and two vertices are adjacent if they commute. The commuting graph of a group appears to have first been studied in Brauer and Fowler’s paper `On groups of even order‘. Though they don’t actually use the words “commuting graph” they do study the distance between two elements of the group in what would be the commuting graph.

My interest in commuting graphs was piqued by the paper `On the commuting graph associated with the symmetric and alternating groups‘ by Iranmanesh and Jafarzadeh. This paper shows that when the commuting graph of the alternating group is connected it has diameter at most 5. They also make the following conjecture:

There is an absolute constant

csuch that if the commuting graph of a finite group is connected, it has diameter at mostc.

Further supporting evidence for this conjecture is in the paper `Anisotropic groups of type and the commuting graph of finite simple groups‘ by Yoav Segev and Gary Seitz, which shows that for all finite classical simple groups over a field of size at least 5, if the commuting graph is connected it has diameter at most 10. The bound on the field size is mainly there so that they can give necessary and sufficient conditions for when the graph is connected. Looking at their proof, it is possible to show that the commuting graph of *GL(n,2)* has diameter at most 8.

Moreover, in their paper `On the diameters of commuting graphs‘, Akbari, Ghandehari, Hadian and Mohammadian, show that for a field *F* of size at least 3, if the commuting graph of *GL(n,F) *is connected it has diameter at most 6. This is not sharp and the authors conjecture that it is actually at most 5. It is shown in `Commuting graphs of matrix algebras‘ by Akbari, Bidkorii and Mohammadian that the commuting graph of *GL(n,q) *for is connected if and only if *n *is not a prime, while for *GL(n,2) *it* *is connected if and only if *n *and *n-1 *are both not primes.

Instead of looking at matrix groups over fields, we looked at matrix groups over the integers modulo m. The main result is that for a composite integer m, the commuting graph of is connected and has diameter 3.

The commuting graph of a ring can be similarly defined and the commuting graph of is also connected and has diameter 3.

Aedan also conducted some computer calculations of the diameters of commuting graphs for small groups using the small group database which is available in Magma. Despite searching through all groups of order up to 2000 except for those of the form for *k* composite and not equal to 9 or 4, no graph of diameter larger than 6 was found. We do not know whether or not the upper bound on 8 for the diameter of the commuting graph of *GL(n,2) *is sharp, so it would be interesting to see if we can find examples of groups which have a commuting graph with diameter greater than 6.

Interestingly, no graph of diameter 2 was found either. In fact Segev, in `The commuting graph of minimal nonsolvable groups‘ has shown that the commuting graph of a finite minimal nonsoluble group has diameter at least 3. It is not possible to have a group whose commuting graph is complete (as the vertices of the commuting graph are not in the centre of the group) but is there one for which the diameter is 2?

Correction: There are groups for which the commuting graph has diameter 2. For example, group number 176 of the groups of order 486 in Magma has diameter 2. Thank you to Pablo Spiga and Gabriel Verret for pointing this out. It turns out that Aedan’s code did determine that this group, and a few others, have diameter 2 but we missed them when searching through all the data.

Dear Michael,

I also noticed this. Here is I think an “explicit” example of a group whose commuting graph has diameter 2. G is nilpotent class 2, the centre is elementary abelian of order 2^5, generated by z_1,…,z_5, and G/Z(G) is elementary abelian of order 2^4, generated by x_1,x_2,x_3,x_4, so that x_i ^2 = z_i, for i = 1,…,4. The commutator relations are [x_1,x_2]=[x_2,x_3]=[x_3,x_4]=[x_4,x_1] = 1, and [x_1,x_3]=[x_2,x_4] = z_5. The commuting graph of G can be reduced to a graph on the 15 points x_1,…,x_4, x_1 x_2,…, x_1 x_2 x_3 x_4 and its just a matter of checking that the diameter is 2. This group is, in some sense, that whose commuting graph is as close as possible to being complete without actually being so. If one tried to do the same thing for only 3 generators of G/Z(G), then it wouldn’t work.

Dear Michael,

I was reading this blog just recently and noticed the same thing. Here is an “explicit” example of group whose commuting graph has diameter 2. G is nilpotent of class 2, the center is elementary abelian of order 2^5, generated by z_1,…,z_5, and G/Z(G) is elementary abelian of order 2^4, generated by x_1,…,x_4 such that x_i ^2 = z_i for i = 1,…,4. The commutator relations are [x_1,x_2]=[x_2,x_3]=[x_3,x_4]=[x_4,x_1]=1, [x_1,x_3]=[x_2,x_4]=z_5. To determine the structure of the commuting graph, it’s enough to consider the graph formed by the 15 vertices x_1,x_2,x_3,x_4,x_1 x_2,….,x_1 x_2 x_3 x_4. It’s then just a matter of checking that the commuting graph has diameter 2. This group seems to me to be the one whose commuting graph is “as close as possible” to being complete without actually being so. If one tried to do something similar with just 3 generators for G/Z(G), then it wouldn’t work : either the graph would be disconnected or something would be connected to everything.

Some recent results:

The exact value of the diameter of the commuting graph of when it is connected has been determined to be 5 by David Dolzan and Polona Oblak.

There is also a preprint on the arxiv by Joao Araujo, Michael Kinyon, Janusz Konieczny, that shows that for all positive integers n there is a semigroup S such that the diameter of the commuting graph of S is n.

But the problem is still open for groups then ? I haven’t found anything more recent than this paper for semigroups.

Aedan has some more results in his honours dissertation but it is still open for groups.

Dear Michael,

Dolzan-Oblak’s claim that “The exact value of the diameter of the commuting graph of S_n when it is connected is 5” is correct (I think), but their proof appears to contain a gap.

Please see http://arxiv.org/abs/1205.1664

(page 25).

The exact value for the commuting graph for S_n was also determined in Timothy Woodcock’s PhD thesis, which is available at

here.

Just to finish my comments on this topic, I was considering a related problem : What is the smallest order, say g(n), of a finite group, whose commuting graph contains every graph on n vertices, up to isomorphism, as an induced subgraph ? It’s easy to see that g(n) must at least be exponential in n, as the same is true, by a simple counting argument, for any graph which contains every n-vertex graph as an induced subgraph. It is known that there are graphs on slightly more than 2^{n/2} vertices containing all n-vertex graphs as induced subgraphs, and one easily use this fact to construct a nilpotent-class-2 example which shows that g(n) is at most doubly exponential in n. So my basic question would be : Is g(n) exponential in n ?