ISOMORPHISM-CLASSES OF CYCLE PERMUTATION GRAPHS

Abstract

In this paper, we construct a cycle permutation graph as a covering graph over the dumbbell graph, and give a new characterization of when two given cycle permutation graphs are isomorphic by a positive or a negative natural isomorphism. Also, we count the isomorphism classes of cycle permutation graphs up to positive natural isomorphism, and find the number of distinct cycle permutation graphs isomorphic to a given cycle permutation graph by a positive/negative natural isomorphism. As a consequence, we obtain a formula for finding the number of double cosets of the dihedral group in the symmetric group.