Total relative displacement of vertex permutations of K n 1 , n 2 , …, n t
Total relative displacement of vertex permutations of K n 1 , n 2 , …, n t
复制标题
K n 1 , n 2 , …, n t 顶点排列的总相对位移
DOI：
10.1002/jgt.v41:2
复制
发表时间：
2002
影响因子：
0.9
通讯作者：
Xingxing Yu
中科院分区：
文献类型：
--
作者：
Laura Sheppardson;Xingxing Yu
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 ne permutations α of the vertices of G. A permutation α for which π(G) = δα(G) has been called a near-automorphism of G [2]. We determine π(Kn1,n2,…,nt) and describe permutations α of Kn1,n2,…,nt for which π(Kn1,n2,…,nt) = δα(Kn1,n2,…,nt). 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,$\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 k0 is the smallest index for which nk0+1 = nk0+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
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 ne permutations α of the vertices of G. A permutation α for which π(G) = δα(G) has been called a near-automorphism of G [2]. We determine π(Kn1,n2,…,nt) and describe permutations α of Kn1,n2,…,nt for which π(Kn1,n2,…,nt) = δα(Kn1,n2,…,nt). 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,$\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 k0 is the smallest index for which nk0+1 = nk0+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