Routing in Cycles via Matchings

ABSTRACT Let be a graph with vertices labeled , and let be a permutation on . Initially, a pebble is placed at vertex , with destination for each . At each step, we select a matching in and swap the two pebbles on each edge of the matching. The routing number for , denoted , is the minimum number of steps required for all pebbles to reach their destinations. Li, Lu, and Yang 2010 proved that for every permutation on the ‐cycle . They conjectured that for , if , then or its inverse. He, Valentin, Yin, and Yu 2016 proved that this conjecture holds for all even . In this paper, we prove the conjecture holds for all .