1 References

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(Cn) = n − 1 (for n ≥ 3) and for s ≥ t, rt(Ks,t) = b 3s2t c+ O(1). We also prove n + 1 ≤ rt(Qn) ≤ 2n − 2 for n ≥ 3. The lower bound rt(Qn) ≥ n + 1 was previously conjectured by Alon, Chung and Graham. A variation so called fractional routing number is also considered in this paper