Isomorphism Classes of Bipartite Cycle Permutation Graphs

Abstract

In this paper, we count the number of isomorphism classes of bipartite $n$-cyclic permutation graphs up to positive natural isomorphism and show that it is equal to the number of double cosets of the dihedral group $D_n$ in the subgroup $B_n$ of the symmetric group $S_n$, consisting of parity-preserving or parity-reversing permutations.