Journal of Combinatorics
Volume 11 (2020)
Routing number of dense and expanding graphs
Pages: 329 – 350
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.
routing number, spectral graph theory, disjoint paths
2010 Mathematics Subject Classification
05C12, 05C35, 05C38, 05C50
Research funded in part by Simons Collaboration Grant #525039.
Received 1 September 2018
Published 14 January 2020