Near automorphisms of cycles (Q2469986): Difference between revisions

Let \(f\) be a permutation of the vertex set \(V(G)\) of a connected finite simple graph \(G\). Let \(\delta_f(G)=\sum_{x,y\in V(G)}| d_G(x,y)-d_G(f(x),f(y))| \), where the sum is over all unordered pairs of vertices. It is clear that \(f\) is an automorphism of \(G\) if and only if \(\delta_f(G)=0\). By a near automorphism of \(G\) the authors mean a permutation \(f\) for which \(\delta_f(G)\) takes the smallest possible strictly positive value, this value is denoted \(\pi(G)\). This quantity has been computed for a path by \textit{W. Aitken} [J. Comb. Theory, Ser. A 87, No.~1, 1--21 (1999; Zbl 0937.05001)], and for a complete multipartite graphs by \textit{K. B. Reid} [J. Graph Theory 41, No.~2, 85--100 (2002; Zbl 1020.05034)]. The purpose of this paper is to prove that \(\pi(C_n)=4\lfloor n/2\rfloor -4\) and to describe the set of near automorphisms of \(C_n\), where \(C_n\) is a cycle of length \(n\).