Isomorphism classes of cycle permutation graphs (Q1199480)

G. Chartrand and F. Harary introduced permutation graphs as a generalization of the well-known Petersen graph. The authors construct a cycle permutation graph as a covering graph over the dumbbell graph. They also give a new characterization of the case when two given cycle permutation graphs are isomorphic by a positive or a negative natural isomorphism. The authors present a complete numerical counting of the isomorphism classes of cycle permutation graphs up to positive natural isomorphism. This gives a formula for finding the number of double cosets of the dihedral group in the symmetric group.