{
  "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)\\leqγ_b(G)$. In 2014, Hartnell and Mynhardt proved that $γ_b(G)\\leq 3mp(G)-2$ whenever $mp(G)\\geq2$. In 2019, Beaudou, Brewster, and Foucaud improved this bound to $γ_b(G)\\leq 2 mp(G)+3$ and conjectured that $γ_b(G)\\leq 2 mp(G)$. We solve their conjecture by proving that $γ_b(G)\\leq 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)$.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.20036",
  "author_total": 1,
  "authors": [
    {
      "name": "Sk Samim Islam"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/d5xjnzh3m38fp.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.20036",
  "fulltext_url": null,
  "id": "d5xjnzh3m38fp",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.20036",
  "language": null,
  "licence": "CC-BY-NC-ND-4.0",
  "licence_label": "CC BY-NC-ND 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-nc-nd/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7203926932",
  "pdf_url": "https://arxiv.org/pdf/2608.20036",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-23",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/d5xjnzh3m38fp.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:35:19Z",
      "native_id": "2608.20036",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.20036"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Broadcast Domination Number is at Most Twice the Multipacking Number",
  "title_text": "Broadcast Domination Number is at Most Twice the Multipacking Number",
  "type": "preprint",
  "updated_at": "2026-10-30T12:35:19Z",
  "url": "https://research.draconitic.com/paper/d5xjnzh3m38fp",
  "venue": "arXiv",
  "versions": []
}