Premium
Near‐automorphisms of paths
Author(s) -
Chang Gerard J.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20561
Subject(s) - combinatorics , mathematics , automorphism , permutation (music) , graph , graph theory , permutation group , path (computing) , discrete mathematics , computer science , physics , acoustics , programming language
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