On natural isomorphisms of cycle permutation graphs (Q1115888)

Two problems are approached in this paper. Given a permutation on n elements, which permutations on n elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs is isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.