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

arXiv:2610.39469 · math.CO · Submitted 2026-10-29 · Read on arXiv

math.CO

Submitted: 2026-10-29

Updated: 2026-10-29

Comments: 128 pages, 9 figures. Explicit extremal classification with reproducible computational certificates and partial Lean verification. Companion: https://angelraychev.com/cop-prisoner/

License: http://creativecommons.org/licenses/by/4.0/

The gist: A messenger and a pursuer move alternately on a finite loopless directed graph, with complete information and waiting permitted.

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 at least12, a piecewise formula describes sparse growth, the interval 2n at most m at most 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 at least12 and m at least24, the claimed scores of prescribed constructions at every admissible pair, and further finite upper bounds. Its remaining obligations are stated separately.

Related papers