Routing number of dense and expanding graphs

Consider a connected graph $G$, with a pebble placed on each vertex of $G$. The routing number, $rt(G)$, of $G$ is the minimum number of steps needed to route any permutation on the vertices of $G$, where a step consists of selecting a matching in the graph and swapping the pebbles on the endpoints of each edge. Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 516–530.] introduced this parameter, and (among other results) gave a bound based on the spectral gap for general graphs. The bound they obtain is polylogarithmic for graphs with a sufficiently strong spectral gap. In this paper, we use spectral properties and probablistic methods to investigate when this upper bound can be improved to be constant depending on the gap and the vertex degrees.

Keywords

routing number, spectral graph theory, disjoint paths

2010 Mathematics Subject Classification

05C12, 05C35, 05C38, 05C50

Full Text (PDF format)

Research funded in part by Simons Collaboration Grant #525039.

Received 1 September 2018

Published 14 January 2020