Broadcast Domination Number is at Most Twice the Multipacking Number
Abstract
For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast f is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of G, denoted by $ γ_{b}(G) $. A multipacking is a set $ M \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ M $, that is, there are at most $ r $ vertices in $ M $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. It is known that mp(G)≤γb(G). In 2014, Hartnell and Mynhardt proved that γb(G)≤ 3mp(G)−2 whenever mp(G)≥2. In 2019, Beaudou, Brewster, and Foucaud improved this bound to γb(G)≤ 2 mp(G)+3 and conjectured that γb(G)≤ 2 mp(G). We solve their conjecture by proving that γb(G)≤ 2 mp(G) for every graph G. Our proof is constructive and yields a linear-time $2$-approximation algorithm for Maximum Multipacking problem which improves the earlier approximation factor 2+o(1).
Related
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Bounds for the ratio between the independent domination number and the domination number
- On Alon's problem concerning the difference between connected domination number and domination number
- The domination number of the $2$-token graph of path graphs
- Graphs with Large Vertex–Edge Roman {2}-Domination Number
BibTeX
@misc{islam2026broadcast,
title = {{Broadcast Domination Number is at Most Twice the Multipacking Number}},
author = {Sk Samim Islam},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.20036},
eprint = {2608.20036},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20036},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Broadcast Domination Number is at Most Twice the Multipacking Number
AU - Sk Samim Islam
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2608.20036
UR - https://arxiv.org/abs/2608.20036
AB - For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast f is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of G, denoted by $ γ_{b}(G) $. A multipacking is a set $ M \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ M $, that is, there are at most $ r $ vertices in $ M $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. It is known that mp(G)≤γ_b(G). In 2014, Hartnell and Mynhardt proved that γ_b(G)≤ 3mp(G)−2 whenever mp(G)≥2. In 2019, Beaudou, Brewster, and Foucaud improved this bound to γ_b(G)≤ 2 mp(G)+3 and conjectured that γ_b(G)≤ 2 mp(G). We solve their conjecture by proving that γ_b(G)≤ 2 mp(G) for every graph G. Our proof is constructive and yields a linear-time $2$-approximation algorithm for Maximum Multipacking problem which improves the earlier approximation factor 2+o(1).
ER -