Abstract: | Let α denote a permutation of the n vertices of a connected graph G. Define δα(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δα(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δα(G) = 0. Let π(G) denote the smallest positive value of δα(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δα(G) has been called a near‐automorphism of G 2 ]. We determine π(K ) and describe permutations α of K for which π(K ) = δα(K ). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to ni,1≤i≤t. We prove that for positive integers, n1≤n2≤…≤nt, where t≥2 and nt≥2, where k0 is the smallest index for which n = n +1. As a special case, we correct the value of π(Km,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002 |