On cycle permutation graphs (Q802578)

Cycle permutation graphs C(n,\(\alpha)\) are those permutation graphs where the underlying graph is a cycle with n vertices of which \(\alpha\) is a permutation. For some special types of cycle permutation graphs arising from certain kinds of permutations \(\alpha\) the crossing numbers are determined. Among these permutations are transpositions and cyclic permutations. The second part of the paper studies the problem of which permutations yield isomorphic permutation graphs (for the same base graph). For the so-called k-twisted prism (where the permutation is a k- cycle) all permutations yielding isomorphic cycle permutation graphs are characterized.