Metraipolis › archive › dc_afbf7751ec39
Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions — arXiv:2610.39469
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.39469
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:37:55.011Z
- SHA-256 of the archived text
8f999e9081a873609a2455973bf30328b366a4d11bcbb3a5008d50c2c7d9ab94- Stable URL of this page
https://metraipolis.com/documento/dc_afbf7751ec39
How to cite
Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions — arXiv:2610.39469 — arXiv (en), https://arxiv.org/abs/2610.39469 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_afbf7751ec39 (Metraipolis archive dc_afbf7751ec39, sha256 8f999e9081a873609a2455973bf30328b366a4d11bcbb3a5008d50c2c7d9ab94)
BibTeX
@misc{dcafbf7751ec39,
title = {Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions — arXiv:2610.39469},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.39469},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_afbf7751ec39; sha256 8f999e9081a873609a2455973bf30328b366a4d11bcbb3a5008d50c2c7d9ab94},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39469. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A messenger and a pursuer move alternately on a finite loopless directed graph, with complete information and waiting permitted. The messenger moves first and wins upon reaching a designated recipient, before interception there. We determine the maximum number $M(n,m)$ of ordered nonadjacent source--recipient pairs for which delivery is guaranteed against every initial pursuer position, among graphs with $n$ vertices and $m$ arcs. We give the exact value and an explicit attaining graph for every admissible pair $(n,m)$. For $n\ge12$, a piecewise formula describes sparse growth, the interval $2n\le m\le n(n-3)$ in which every missing pair can be guaranteed, a dense staircase, and the zero range above $n(n-2)$. Complete finite tables cover smaller orders. The proofs combine degree and support bounds, local strategy composition, protected routing, and constructions in the missing-arc graph. Finite exceptional cases use explicit strategy certificates and complete computational exclusions. Reproducible programs and certificates accompany the paper; a Lean development verifies the complete formula for $n\ge12$ and $m\ge24$, the claimed scores of prescribed constructions at every admissible pair, and further finite upper bounds. Its remaining obligations are stated separately. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.39469 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-01T02:15:28.273Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).