Geodesic
Permutations in two dimensions that maximally separate neighbors
The electronic journal of combinatorics, Tome 26 (2019) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We characterize all permutations on even-by-even grids that maximally separate neighboring vertices. More precisely, let $n_1$, $n_2$ be positive even integers, let $I(n_1,n_2)=\{1,\dots,n_1\}\times\{1,\dots,n_2\}$ be the $n_1\times n_2$ grid, let $\mathrm{d}$ be the $L_1$ metric on $I(n_1,n_2)$, and let $N=\{\{x,y\}\in I(n_1,n_2)\times I(n_1,n_2): \mathrm{d}(x,y)=1\}$ be the set of neighbors in $I(n_1,n_2)$. We characterize all permutations $\pi$ of $I(n_1,n_2)$ that maximize $\sum_{\{x,y\}\in N} \mathrm{d}(\pi(x),\pi(y))$.
DOI : 10.37236/8148
Classification : 05A05
Mots-clés : permutation, total displacement

Mohammed Albow    ; Jeffrey Edgington    ; Mario Lopez    ; Petr Vojtěchovský  1

1 University of Denver 
@article{10_37236_8148,
     author = {Mohammed Albow and Jeffrey Edgington and Mario Lopez and Petr Vojt\v{e}chovsk\'y},
     title = {Permutations in two dimensions that maximally separate neighbors},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {2},
     doi = {10.37236/8148},
     zbl = {1473.05004},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8148/}
}
TY  - JOUR
AU  - Mohammed Albow
AU  - Jeffrey Edgington
AU  - Mario Lopez
AU  - Petr Vojtěchovský
TI  - Permutations in two dimensions that maximally separate neighbors
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8148/
DO  - 10.37236/8148
ID  - 10_37236_8148
ER  - 
%0 Journal Article
%A Mohammed Albow
%A Jeffrey Edgington
%A Mario Lopez
%A Petr Vojtěchovský
%T Permutations in two dimensions that maximally separate neighbors
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8148/
%R 10.37236/8148
%F 10_37236_8148
Mohammed Albow; Jeffrey Edgington; Mario Lopez; Petr Vojtěchovský. Permutations in two dimensions that maximally separate neighbors. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/8148

Cité par Sources :