# 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^{} ${\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 ${\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.

### 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 |