Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
Abstract
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≥12, a piecewise formula describes sparse growth, the interval 2n≤ m≤ 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≥12 and m≥24, the claimed scores of prescribed constructions at every admissible pair, and further finite upper bounds. Its remaining obligations are stated separately.
Related
- The Stability and Density of Norm Attaining Operators on Reducing Subspaces
- On 2-Sphere Bowditch Boundaries Attaining Conformal Dimension
- A characterization of graphs attaining a lower bound on the dissociation number
- CPM-LDPC Codes Attaining the Minimum-Distance Bound
- Minimum attaining operators on reducing subspaces: Spectral structure and density
BibTeX
@misc{raychev2026guaranteed,
title = {{Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions}},
author = {Angel Ivanov Raychev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39469},
eprint = {2610.39469},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39469},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
AU - Angel Ivanov Raychev
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39469
UR - https://arxiv.org/abs/2610.39469
AB - 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≥12, a piecewise formula describes sparse growth, the interval 2n≤ m≤ 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≥12 and m≥24, the claimed scores of prescribed constructions at every admissible pair, and further finite upper bounds. Its remaining obligations are stated separately.
ER -