Total relative displacement of vertex permutations of K

✍ Scribed by K. B. Reid

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 167 KB
• Volume: 41
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10078

✦ Synopsis

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) 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 __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,
where k~0~ is the smallest index for which n = n+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