{"id":"arxiv/2603.04344","url":"https://arxiv.org/abs/2603.04344","tags":["math.CO"],"score":0,"title":"All-to-all Routing on Kautz Graphs: Regular Routing Beats Shortest Paths","domain":"math.CO","source":"arxiv","authors":["Vance Faber","Noah Streib"],"reviews":0,"subject":"math.CO","summary":"We study packet routing in the Kautz digraph K(d,D), where every ordered pair of distinct vertices is connected by a unique shortest directed path. The regular routing introduced in earlier work schedules all ordered pairs in tau(d,D) = (D-1)d^(D-2) + D d^(D-1) steps. We show that, for every fixed outdegree d at least 2 and all sufficiently large diameters D, no shortest-path routing scheme can match this makespan. More precisely, we prove that K(d,D) contains an edge whose shortest-path congestion strictly exceeds tau(d,D) when D is sufficiently large. Our construction uses edge-words drawn…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-04","reactions":{}}