Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions

Source 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\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.