Extremal permutations in routing cycles (Q727043)

Summary: Let \(G\) be a graph whose vertices are labeled \(1\),\dots, \(n\), and \(\pi\) be a permutation on \([n]:=\{1,2,\dots, 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 \(\mathrm{rt}(G, \pi)\), the routing number for \(\pi\), be the minimum number of steps necessary for the pebbles to reach their destinations.{ }\textit{W.-T. Li} et al. [SIAM J. Discrete Math. 24, No. 4, 1482--1494 (2010; Zbl 1221.05212)] proved that \(\mathrm{rt}(C_n, \pi)\leq n-1\) for every permutation \(\pi\) on the \(n\)-cycle \(C_n\) and conjectured that for \(n\geq 5\), if \(\mathrm{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\geq 6\).