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 bethe non-commuting graph of $G$.The non-commuting graph ${\mathrm{\Gamma }}_G$ was first considered by PaulErdös, when he posed the following problem in 1975 [B.H. Neumann, A problem of Paul Erdös ongroups, J. Austral. Math. Soc. Ser. A 21 (1976), 467-472]:
Let$G$ be a group whose non-commuting graph has no infinite completesubgraph. Is it true that there is a finite bound on thecardinalities 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$, orthe 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 cyclenotation, we have

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

The center is trivial: $Z(S_3)=\{()\}$. The non-commuting graph inFigure 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, isthe symmetry group of the http://planetmath.org/node/1086square. If you label the vertices of thesquare from $1$ to $4$ going along the edges, the octic group may beseen 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 centerconsists of the identity element and the simultaneous flip around bothdiagonals $(13)(24)$. Its non-commuting graph is given inFigure 2.

Figure 2: Non-commuting graph of the octic group