Routing Numbers of Cycles, Complete Bipartite Graphs, and Hypercubes

Abstract

The routing number $rt(G)$ of a connected graph G is the minimum integer r so that every permutation of vertices can be routed in r steps by swapping the ends of disjoint edges. In this paper, we study the routing numbers of cycles, complete bipartite graphs, and hypercubes. We prove that $rt(C_n)=n-1$ (for $n\geq3$) and for $s\geq t$, $rt(K_{s,t})=\lfloor\frac{3s}{2t}\rfloor+O(1)$. We also prove $n+1\leq rt(Q_n)\leq2n-2$ for $n\geq3$. The lower bound $rt(Q_n)\geq n+1$ was previously conjectured by Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 513–530]. A variation, called fractional routing number, is also considered in this paper.