Near‐automorphisms of paths |
| |
| Authors: | Gerard J. Chang |
| |
| Affiliation: | 1. Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan;2. Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan;3. National Center for Theoretical Sciences, Taipei Office, Taipei, Taiwan |
| |
| Abstract: | 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 π(Pn) = 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. J Graph Theory 68:323‐325, 2011 |
| |
| Keywords: | permutation near‐automorphism path |
|
|
