Journal of the
Korean Mathematical Society JKMS

In this paper, we study the isomorphism problem of Cayley permutation graphs. We obtain a necessary and sufficient condition that two Cayley permutation graphs are isomorphic by a direction-preserving and color-preserving (positive/negative) natural isomorphism. The result says that if a graph $G$ is the Cayley graph for a group $\Gamma$ then the number of direction-preserving and color-preserving positive natural isomorphism classes of Cayley permutation graphs of $G$ is the number of double cosets of $\Gamma^\ell$ in $S_\Gamma$, where $S_\Gamma$ is the group of permutations on the elements of $\Gamma$ and $\Gamma^\ell$ is the group of left translations by the elements of $\Gamma$. We obtain the number of the isomorphism classes by counting the double cosets.

Keywords: Cayley permutation graph, isomorphism

MSC numbers: 05C60, 05C25