2014/04/07 by Junhua He, Louis A. Valentin, He, Junhua +5
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #math.CO
paper · pdf · doi:10.48550/arxiv.1404.1851
openalex publication_date 2014/04/07 · arxiv created 2016/08/31 · arxiv updated 2016/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let G be a graph on n vertices, labeled v1,…,vn and π be a permutation on [n]:=\1,2,⋯, n\. Suppose that each pebble pi is placed at vertex vπ(i) and has destination vi. During each step, a disjoint set of edges is selected and the pebbles on each edge are swapped. Let rt(G, π), the routing number for π, be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang prove that rt(Cn, π)≤ n-1 for any permutation on n-cycle Cn and conjecture that for n ≥ 5, if rt(Cn, π) = n-1, then π= (123⋯ 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.