Total relative displacement of vertex permutations of K n 1 , n 2 , …, n t

Abstract Let α denote a permutation of the n vertices of a connected graph G . Define δ α ( G ) to be the number $\sum |d(x,y)-d(\alpha (x),\alpha(y))|$ , where the sum is over all the $\left({n \atop 2} \right)$ 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   n   1 , n   2 ,…, n   t) and describe permutations α of K   n   1 , n   2 ,…, n   tfor which π( K   n   1 , n   2 ,…, n   t) = δ α ( K   n   1 , n   2 ,…, n   t). 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 i th row and the sum of the entries in the i th column each equal to n i ,1≤ i ≤ t . We prove that for positive integers, n 1 ≤ n 2 ≤…≤ n t , where t ≥2 and n t ≥2,$\pi {(K_{n_1 ,{n}_2 , \ldots ,{n}_t} }) = \left \{\matrix{2{ n}_{ h + 1} - 2\hfill \quad\quad{\rm if} \,\,\, 1 = { n}_1 = { n}_2 = \cdots = {n_h} < { n}_{{ h} + 1}\hfill \cr \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\le \cdots \le { n}_{t} , {\rm and}\ {t}\ge(h + 1),\hfill\cr \quad\quad\quad\quad\quad\quad{\rm for\ some} \ { h}\ge 2,\hfil \cr 2{ n}_{{ k}_0}\hfill \quad\quad\quad\quad\quad\quad\quad{\rm if} \,\,\, 1 = {n_1} < { n}_2\ {\rm or}\ { n}_1 \ge 2, {n}_{{ k} + 1} = {n}_{ k} + 1,\hfill \cr \;\quad\quad\quad\quad\quad{\rm\ for\ some}\ k, 1\le { k} \le { t} - 1,\ \cr \;\quad\quad\quad\quad{\rm and}\ 2+ { n}_{{ k}_0 } \le { n}_1 + { n}_2 , \cr 2({ n}_1 + { n}_2 - 2)\hfill {\rm otherwise},\hfill\hfill\hfill\hfill\hfill\cr } \right.$where k 0 is the smallest index for which n   k   0 +1  =  n   k   0+1. As a special case, we correct the value of π( K m , 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