Near automorphisms of cycles

Abstract

Let f be a permutation of V (G). Define delta(f)(x, y) = vertical bar d(G)(x, y) -d(G) (f (x), f (y))vertical bar and delta(f)(G) = Sigma delta(f)(x, y) over all the unordered pairs {x, y} of of distinct vertices of G. Let pi(G) denote the smallest positive value of delta(f)(G) among all the permutations f of V (G). The permutation f with delta(f) (G) = pi(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles C and we prove that pi(C-n) = 4[n/2] - 4, moreover, we obtain the set of near automorphisms of C-n. (C) 2007 Elsevier B.V. All rights reserved.