Extremal permutations in routing cycles

Abstract

Let $G$ be a graph on $n$ vertices, labeled $v_1,\dots ,v_n$ and $\pi$ be a permutation on $[n]:=\{1,2,\cdots ,n\}$. Suppose that each pebble $p_i$ is placed at vertex $v_{\pi (i)}$ and has destination $v_i$. During each step, a disjoint set of edges is selected and the pebbles on each edge are swapped. 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 prove that $rt(C_n,\pi )\le n-1$ for any permutation on $n$-cycle $C_n$ and conjecture that for $n\ge 5$, if $rt(C_n,\pi )=n-1$, then $\pi =(123\cdots n)$ or its inverse. By a computer search, they show that the conjecture holds for $n<8$. We prove in this paper that the conjecture holds for all even $n$.