Near‐automorphisms of paths

The total relative displacement of a permutation f of vertices of a connected graph G is , where the sum is taken over all unordered pairs of distinct vertices of G . Let π( G ) denote the smallest positive value of δ f ( G ) among the n ! permutations f . Aitken [J Combin Theory Series A 87 (1999), 1–21] proved that π( P n ) = 2 n − 4 for the n ‐path P n , which was conjectured by Chartrand et al. [Proceedings of the 1996 Eighth Quadrennial International Conference on Graph Theory, Combinatorics Algorithms, and Applications I, New Issues Press, Kalamazoo, 1999, pp. 181–192]. This article gives a short proof of the result. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:323‐325, 2011