non-commuting graph
Let be a non-abelian group with center . Associate a graph
with whose vertices are the non-central elements
and whose edges join those vertices for which . Then is said to be
the non-commuting graph of .
The non-commuting graph 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
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 ?
B. H. Neumann answered positively Erdös’ question.
The non-commuting graph of a non-abelian group is always connected with diameter 2 and girth 3.
It is also Hamiltonian. is planar if and only if is isomphic to the symmetric group , or
the dihedral group of order or the quaternion group of order .
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 .
Examples
Symmetric group
The symmetric group is the smallest non-abelian group. In cycle notation, we have
The center is trivial: . The non-commuting graph in Figure 1 contains all possible edges except one.
Octic group
The dihedral group , 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 to going along the edges, the octic group may be seen as a http://planetmath.org/node/1045subgroup of the symmetric group :
So the octic group has http://planetmath.org/node/2871order (hence its name), and its center consists of the identity element and the simultaneous flip around both diagonals . 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 |