Let $G$ be a graph whose vertices are labeled $1,\ldots,n$, and $\pi$ be a permutation on $[n]:=\{1,2,\ldots, n\}$. A pebble $p_i$ that is initially placed at the vertex $i$ has destination $\pi(i)$ for each $i\in [n]$. At each step, we choose a matching and swap the two pebbles on each of the edges. Let $rt(G, \pi)$, the routing number for $\pi$, be the minimum number of steps necessary for the pebbles to reach their destinations.Li, Lu and Yang proved that $rt(C_n, \pi)\le n-1$ for every permutation $\pi$ on the $n$-cycle $C_n$ and conjectured that for $n\geq 5$, if $rt(C_n, \pi) = n-1$, then $\pi = 23\cdots n1$ or its inverse. By a computer search, they showed that the conjecture holds for $n<8$. We prove in this paper that the conjecture holds for all even $n\ge 6$.
@article{10_37236_5422,
author = {Jinhua He and Louis A. Valentin and Xiaoyan Yin and Gexin Yu},
title = {Extremal permutations in routing cycles},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5422},
zbl = {1351.05214},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5422/}
}
TY - JOUR
AU - Jinhua He
AU - Louis A. Valentin
AU - Xiaoyan Yin
AU - Gexin Yu
TI - Extremal permutations in routing cycles
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5422/
DO - 10.37236/5422
ID - 10_37236_5422
ER -
%0 Journal Article
%A Jinhua He
%A Louis A. Valentin
%A Xiaoyan Yin
%A Gexin Yu
%T Extremal permutations in routing cycles
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5422/
%R 10.37236/5422
%F 10_37236_5422
Jinhua He; Louis A. Valentin; Xiaoyan Yin; Gexin Yu. Extremal permutations in routing cycles. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5422
