On mapping graphs and permutation graphs

Abstract

We consider finite simple graphs and the terminology of Harary [4] and Behzad—Chartrand [1] is used. Permutation graphs have been studied in several contexts, compare [2, 3]. For completeness we recall the definiton. Let X = (V, E) be a graph with vertex-set V={vu..., vn) and edge-set E and p a permutation of V. Then the permutation graph (X, p) is defined in the following way: V(X, p) = {vl9..., vn9 wx...., wn} = V u V with V ' = {w „..., w„}, V 'nV = 0and E(X9p) = E(X)Kj{[wi9wi] \\[vi9 vi]eE(X)} u u{[^«, Wj] \\ vj=pvi}=EuE'uEp withE ' = {[wt, w,] \\[vi9Vj]eE} andEp = {[vi9 wi]\\pvi = vi}. In general we shall keep this notation with the exception that an arbitrary edge of Ep will be denoted as [JC, px]9 p being considered thereby as a mapping from V onto V. Further, if x e V, then by x ' we denote the corresponding element of V, i.e. if JC = vi9 then x ' = wt. This means we take a second disjoint copy X ' of X and join every vertex of X' with its image under p. We are interested in the automorphisms of (X9p) and especially in the question to which extent the automorphism group G(X, p) is determined by the automorphism group G(X). Definition 1. An automorphism q) of (X, p) is called a natural automorphism of