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.

Examples

Symmetric group S3

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

S3={(),(12),(13),(23),(123),(132)}.

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 http://planetmath.org/node/1086square. If you label the vertices of the square from 1 to 4 going along the edges, the octic group may be seen as a http://planetmath.org/node/1045subgroupMathworldPlanetmathPlanetmath of the symmetric group S4:

𝒟8:={(),(13),(24),(12)(34),(13)(24),(14)(23),(1234),(1432)}.

So the octic group has http://planetmath.org/node/2871order 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