Groups

Group
A group $G$ is a set with a binary operation * , such that
1. The set has an identity element $e$ (i.e.,

*** QuickLaTeX cannot compile formula:
g</em>&e=e*<em>g=g

*** Error message:
Misplaced alignment tab character &.
leading text: $g</em>&

$\forall$ $g \in G$ ).
2. Each element $g \in G$ has an inverse $g^{-1}$ (i.e., $g</em>*g^{-1} = g^{-1}*g = e$ ).

Generating Set of a Finite Group
The generating set $S$ is a set of elements in a finite group $G$ such that every element in $G$ is a product of the elements in $S$ . That is, the entire group can be formed using just the elements in $S$ and the group’s operation. A generating set $S$ is closed if for any $s$ in $S$ , $s^{-1}$ $\in$ $S$ .

Groups for $K_{p,p}$
We focused on complete bipartite graphs with a prime number, $p$ , of vertices in each set. Cayley Graphs that represent complete bipartite graphs $K_{p,p}$ use groups that have $2p$ vertices. The only groups with $2p$ vertices are $Z_{2p}$ , $D_p$ , and $Z_2$ x $Z_p$ . We only need to consider $Z_{2p}$ and $D_p$ when making Cayley Maps for $K_{p,p}$ , because $Z_2p$ and $Z_2$ x $Z_p$ are isomorphic, unless $p=2$ , and in that case $D_2$ and $Z_2$ x $Z_2$ are isomorphic.

Cosets
Within each group $G$ there exists a subgroup, and the remaining vertices in the group form a coset, $C$ . $C$ is equal to the closed generating set of $G$ , so its elements are used to form the rotation used in the Cayley Map $C_M(G,\rho)$ . In the context of the complete bipartite graph $K_{p,p}$ , the vertices that are in the same set as the identity element form a subgroup $H$ of order $p$ , and the other $p$ elements form a coset of $H$ .

Cyclic Groups
Suppose $S'$ is a closed generating set for $Z_{2p}$ , and $C_G(Z_{2p},S')$ is a Cayley Graph for $K_{p,p}$ . The only subgroup in $Z_{2p}$ with order $p$ is the set of even numbers ${0, \dots ,2p-2}$ . Therefore, the coset of $Z_{2p}$ , and thus the rotation of $C_M(Z_{2p},\rho)$ , is comprised of all odd numbers $\{1, \dots , 2p - 1\}$ .

Dihedral Group
Suppose $S'$ is a closed generating set for $D_p$ , and $C_G(D_{p},S')$ is a Cayley Graph for $K_{p,p}$ . Since the only subgroup of order $p$ in $D_p$ is the set of rotations, the coset of $D_p$ is the set of reflections. Therefore, $S' = \{ r^if : 0 \le i < p\}$ . Because reflections have order 2, every element in the rotation is of order 2.

Graph Embeddings

Menu