Total relative displacement of vertex permutations of K-n1, (n2),...,(nt)

摘要

Let c, denote a permutation of the n vertices of a connected graph G. Define delta(alpha)(G) to be the number Sigmad(x,y)-d(alpha(x),alpha(y)), where the sum is over all the ((n)(2)) unordered pairs of distinct vertices of G. The number delta(alpha)(G) is called the total relative displacement of alpha (in G). So, permutation alpha is an automorphism of G if and only if delta(alpha)(G)=0. Let pi(G) denote the smallest positive value of delta(alpha)(G) among the nl permutations alpha of the vertices of G. A permutation alpha for which pi(G)=delta(alpha)(G) has been called a near-automorphism of G [2] We determine pi(k(n 1,n 2,...n t)) and describe permutations alpha K-n 1,K-n2,K-...n t for which pi(K-n 1,K-n 2,K-...n t) = deltaalpha(K-n 1,K-n 2,K-...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 tby tmatrices 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 n(jt) 1 less than or equal to i less than or equal to t. We prove that for positive integers, n(1) less than or equal to n(2) < &BULL;&BULL;&BULL; &LE; n(t), where t &GE; 2 and n(t) &GE; 2, [GRAPHICS] 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,K-n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [2]. (C) 2002 Wiley Periodicals, Inc. [References: 2]