Near-automorphisms of paths
Journal
Journal of Graph Theory
Journal Volume
68
Journal Issue
4
Pages
323-325
Date Issued
2011
Author(s)
Chang, Gerard J.
Abstract
The total relative displacement of a permutation f of vertices of a connected graph G is δf (G)=Σ|dG(x,y)-d G (f (x), f (y))|, where the sum is taken over all (2 n ) 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 pi;(P n)=2n-4 for the n-path Pn, 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.
Type
journal article