Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.04344 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912942774026240 |
|---|---|
| author | Faber, Vance Streib, Noah |
| author_facet | Faber, Vance Streib, Noah |
| contents | 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 from a subset of ternary unbordered square-free words, together with a trimming inequality that propagates large congestion at distance D down to shorter distances. Computations for d=2 and small D show that for all D at least 4 there is an edge in K(2,D) with congestion greater than tau(2,D). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04344 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | All-to-all Routing on Kautz Graphs: Regular Routing Beats Shortest Paths Faber, Vance Streib, Noah Combinatorics 05C20, 05C78, 05C21, 05C12 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 from a subset of ternary unbordered square-free words, together with a trimming inequality that propagates large congestion at distance D down to shorter distances. Computations for d=2 and small D show that for all D at least 4 there is an edge in K(2,D) with congestion greater than tau(2,D). |
| title | All-to-all Routing on Kautz Graphs: Regular Routing Beats Shortest Paths |
| topic | Combinatorics 05C20, 05C78, 05C21, 05C12 |
| url | https://arxiv.org/abs/2603.04344 |