An arXiv preprint dated 20 Aug 2026 reports a theorem placing a universal two-to-one limit on two quantities used in graph theory. For every finite, simple, undirected graph G, the broadcast domination number is at most twice the multipacking number, written γb(G) ≤ 2 mp(G).
The result addresses the conjecture posed by the paper: whether any graph could make broadcast domination more than twice its best multipacking value. Under the stated graph assumptions, the reported answer is no. The main proof treats connected graphs, while the authors extend the inequality componentwise to disconnected graphs because both parameters are additive over components.
This is a proof-based result about graph instances, not an estimate drawn from an empirical sample. The paper reports a mathematical theorem under its stated assumptions rather than a measured effect with statistical uncertainty.
The gap the paper closes
The two quantities form a covering-and-packing pairing. The paper formulates broadcast domination as an integer linear program, a formal optimization model, and presents maximum multipacking as the dual integer program. That pairing supplies the framework for comparing the two values.
The paper places its result against a sequence of earlier bounds. It describes a 2014 result of γb(G) ≤ 3 mp(G)−2 when mp(G)≥2, followed by a 2019 bound of γb(G) ≤ 2 mp(G)+3. The conjecture was that the remaining additive term could be removed.
The reported theorem removes that extra term and gives γb(G) ≤ 2 mp(G) for every graph in the stated class. The paper says the factor two is attained by the examples labeled C4 and C5, where γb(G)=2 and mp(G)=1.
The paper also points to a larger family of hypercube examples. In that family, the relevant ratios tend to two even for arbitrarily large multipacking numbers, reinforcing the claim that the bound is not merely a consequence of small examples.
A proof designed to be used
The proof is constructive. It builds a two-path structure and, in the only unresolved construction case, uses a ball-cover argument to add a vertex to the multipacking. The structure is therefore more than an existence proof: it supplies the outline of an algorithm for building a large multipacking.
For a connected graph, the procedure constructs a multipacking M satisfying |M| ≥ mp(G)/2. In ordinary terms, its output is guaranteed to be at least half the size of an optimal multipacking. That is an approximation guarantee, not a claim that the procedure always finds the exact optimum.
The paper also proves that, for a connected graph with radius r, the multipacking number is at least ⌊r/2⌋ — the integer floor of half the radius. This lower bound is part of the structural route from the graph’s geometry to the constructed packing.
Breadth-first search is used to make the construction computationally accessible. The paper says it can compute the radius, the required paths, the relevant balls, and an uncovered vertex in polynomial time.
The presented radius-based implementation runs in O(nm) time for connected graphs, with n and m denoting the numbers of vertices and edges. The paper also states that an omitted refinement gives an O(n+m)-time factor-two approximation for Maximum Multipacking.
The authors describe that algorithmic result as an improvement over an earlier approximation factor of 2+o(1). The advance is therefore both a sharper inequality and a stated guarantee for constructing a reasonably large multipacking.
What remains unresolved
The runtime claims are complexity statements, not reports from a benchmark or a measured performance study. The supplied analysis reports no empirical graph benchmark or measured runtime data for the presented implementation.
There is also a difference in how fully the two algorithmic claims are developed. The O(nm) radius-based implementation is presented directly, while the linear-time refinement is stated with additional technical lemmas omitted from the supplied account.
The source is identified as arXiv:2608.20036v1, version 1, dated 20 Aug 2026. No peer-reviewed publication details are supplied, so the result should be read as a preprint theorem and algorithmic claim.
The examples showing ratios of two set a limit on the universal inequality, but they do not answer the algorithmic question of whether a polynomial-time approximation better than a factor of two can be found for general graphs.
That question remains open in the paper’s account: can a polynomial-time approximation with a factor strictly below two be achieved for general graphs, or is two the true barrier?
For now, the evidence is confined to finite, simple, undirected graph instances, with connected graphs at the center of the proof and disconnected cases handled componentwise. The result is consequently a statement about the mathematical graph model itself.
Paper data and sources
Original title: Broadcast Domination Number is at Most Twice the Multipacking Number
Authors: Sk Samim Islam
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text