non-commuting graph

Let G be a non-abelian groupMathworldPlanetmath with center Z(G). Associate a graph ΓG with G whose vertices are the non-central elements GZ(G) and whose edges join those vertices x,yGZ(G) for which xyyx. Then ΓG is said to be the non-commuting graph of G. The non-commuting graph ΓG was first considered by Paul Erdös, when he posed the following problem in 1975 [B.H. Neumann, A problem of Paul Erdös on groups, J. Austral. Math. Soc. Ser. A 21 (1976), 467-472]:
Let G be a group whose non-commuting graph has no infiniteMathworldPlanetmath completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath subgraphMathworldPlanetmath. Is it true that there is a finite bound on the cardinalities of complete subgraphs of ΓG?
B. H. Neumann answered positively Erdös’ question.
The non-commuting graph ΓG of a non-abelian group G is always connected with diameter 2 and girth 3. It is also HamiltonianPlanetmathPlanetmath. ΓG is planar if and only if G is isomphic to the symmetric groupMathworldPlanetmathPlanetmath S3, or the dihedral groupMathworldPlanetmath 𝒟8 of order 8 or the quaternion groupMathworldPlanetmathPlanetmath Q8 of order 8.
See [Alireza Abdollahi, S. Akbari and H.R. Maimani, Non-commuting graph of a group, Journal of Algbera, 298 (2006) 468-492.] for proofs of these properties of ΓG.


Symmetric group S3

The symmetric group S3 is the smallest non-abelian group. In cycle notation, we have


The center is trivial: Z(S3)={()}. The non-commuting graph in Figure 1 contains all possible edges except one.

Figure 1: Non-commuting graph of the symmetric group S3

Octic group

The dihedral group 𝒟8, generally known as the octic group, is the symmetry group of the If you label the vertices of the square from 1 to 4 going along the edges, the octic group may be seen as a of the symmetric group S4:


So the octic group has 8 (hence its name), and its center consists of the identity elementMathworldPlanetmath and the simultaneous flip around both diagonals (13)(24). Its non-commuting graph is given in Figure 2.

Figure 2: Non-commuting graph of the octic group
Title non-commuting graph
Canonical name NoncommutingGraph
Date of creation 2013-03-22 15:18:50
Last modified on 2013-03-22 15:18:50
Owner GrafZahl (9234)
Last modified by GrafZahl (9234)
Numerical id 11
Author GrafZahl (9234)
Entry type Definition
Classification msc 20D60
Classification msc 05C25
Synonym non-commuting graph of a group
Related topic NonAbelianTheories
Related topic NonAbelianStructures
Related topic CommutativeVsNonCommutativeDynamicModelingDiagrams
Related topic GeneralizedToposesTopoiWithManyValuedLogicSubobjectClassifiers