non-commuting graph

Let $G$ be a non-abelian group with center $Z(G)$. Associate a graph $\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\neq yx$. Then $\Gamma_{G}$ is said to be the non-commuting graph of $G$. The non-commuting graph $\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 $\Gamma_{G}$?
B. H. Neumann answered positively Erdös’ question.
The non-commuting graph $\Gamma_{G}$ of a non-abelian group $G$ is always connected with diameter 2 and girth 3. It is also Hamiltonian. $\Gamma_{G}$ is planar if and only if $G$ is isomphic to the symmetric group $S_{3}$, or the dihedral group $\mathcal{D}_{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 $\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.

Octic group

The dihedral group $\mathcal{D}_{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}$:

 $\mathcal{D}_{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.

 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