non-commuting graph

Let $G$ be a non-abelian group with center $Z(G)$. Associate a graph ${\mathrm{\Gamma }}_G$ with $G$ whose vertices are the non-central elements $G\setminus Z(G)$ and whose edges join those vertices $x,y\in G\setminus Z(G)$ for which $xy\ne yx$. Then ${\mathrm{\Gamma }}_G$ is said to be the non-commuting graph of $G$. The non-commuting graph ${\mathrm{\Gamma }}_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 infinite complete subgraph. Is it true that there is a finite bound on the cardinalities of complete subgraphs of ${\mathrm{\Gamma }}_G$?
B. H. Neumann answered positively Erdös’ question.
The non-commuting graph ${\mathrm{\Gamma }}_G$ of a non-abelian group $G$ is always connected with diameter 2 and girth 3. It is also Hamiltonian. ${\mathrm{\Gamma }}_G$ is planar if and only if $G$ is isomphic to the symmetric group $S_3$, or the dihedral group ${𝒟}_8$ of order $8$ or the quaternion group $Q_8$ 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 ${\mathrm{\Gamma }}_G$.

Examples

Symmetric group $S_3$

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

$$S_3=\{(),(12),(13),(23),(123),(132)\}.$$

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

Figure 1: Non-commuting graph of the symmetric group ${\mathrm{S}}_{\mathrm{3}}$

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/1045subgroup of the symmetric group $S_4$:

$${𝒟}_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 element 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