Broadcast domination conjecture

The conjecture asks whether every connected graph satisfies $\gamma_b(G)\le 2\operatorname{mp}(G)$, relating broadcast domination to multipacking. Earlier work established only an additive-constant version and left the factor-two bound open.

Known results

• The earlier general bound was $\gamma_b(G)\le 3\operatorname{mp}(G)-2$ when $\operatorname{mp}(G)\ge 2$; Foucaud and coauthors improved it constructively to $\gamma_b(G)\le 2\operatorname{mp}(G)+3$ (2019).
• The conjecture holds for graphs with $\operatorname{mp}(G)\le 4$.
• It holds for hypercubes $Q_n$; there $\gamma_b(Q_n)=n-1$ for $n\ge 3$.
• Stronger bounds are known for special classes, including connected chordal and cactus graphs.

August 2026 claimed resolution

A preprint posted on August 20, 2026, titled “Broadcast Domination Number is at Most Twice the Multipacking Number,” claims a constructive proof of $\gamma_b(G)\le 2\operatorname{mp}(G)$ for all connected graphs. If correct, it resolves the conjecture and removes the additive constant, but the available evidence records no independent verification.

Current status (as of August 2026): The factor-two inequality is claimed in a new preprint but remains unverified; the established general theorem is $\gamma_b(G)\le 2\operatorname{mp}(G)+3$.