Skip to content

Broadcast Domination Number is at Most Twice the Multipacking Number

Aug 2026 · arXiv.org · Vol abs/2608.20036 · 0 citations · 15 references
Computer Science Mathematics

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 $ \gamma_{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\gamma_b(G)$. In 2014, Hartnell and Mynhardt proved that $\gamma_b(G)\leq 3mp(G)-2$ whenever $mp(G)\geq2$. In 2019, Beaudou, Brewster, and Foucaud improved this bound to $\gamma_b(G)\leq 2 mp(G)+3$ and conjectured that $\gamma_b(G)\leq 2 mp(G)$. We solve their conjecture by proving that $\gamma_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)$.

View source

Similar papers

Preprint Oct 2026

Partitioning an $S$-packing coloring into broadcast dominating sets

Given a graph $G$ and a positive integer $k$, a packing $k$-domatic coloring of $G$ is a function $f: V(G) \to \{1,\ldots,t\}$ such that (1) for any color $j \in \{1,\ldots, t\}$ and any two distinct vertices $u,v\in V(G)$ with $f(u)=f(v)=j$ we have $d_G(u,v)>j$, and (2) $V(G)$ admits a partition into $k$ sets $A_1,\ld...

B. Brešar, Jasmina Ferme, Wen-Jie Hu · 0 citations
Open access Sep 2026

Double Total Domination Number of Some Families of Graphs

Let $G$ be a graph of minimum degree at least two. A set $D \subseteq V(G)$ is said to be a \emph{double total dominating set} of $G$, for every vertex $v\in V (G) $ contains at least two neighbors in $D$. The minimum cardinality among all double total dominating sets of $G$ is the \emph{double total domination number}...

Srinu Irugula, P. Francis · 0 citations
Preprint Sep 2026

The VC-dimension of strongly regular graphs

A graph $G$ is $n$-existentially closed or $n$-e.c. if, for all subsets $S\subseteq V(G)$ with $|S|=n$ and for all partitions $S=A\sqcup B$, there exists a vertex in $V(G)\setminus S$ adjacent to all vertices in $A$ and no vertices in $B$. We study the minimum number of edges $m(v,n)$ of a $v$-vertex $n$-e.c. graph, an...

Isabel T. Byrne, John Byrne, S. Cioabă · 0 citations
Preprint Oct 2026

Structural aspects of $1$-limited domination in cubic graphs

A set $D\subseteq V(G)$ is a $1$-limited dominating set of a graph $G$ if every vertex outside $D$ has a neighbor in $D$ and every vertex of $D$ has at most one neighbor outside $D$. The minimum cardinality among all $1$-limited dominating sets of $G$ is denoted by $\gamma_1^{\mathrm L}(G)$. For every cubic graph $G$ o...

Goran Radić, Gordana Radić, Aleksandra Tepeh · 0 citations
Preprint Sep 2026

Sub-quorum colorings of some infinite families of caterpillars

A partition $\pi=\{V_{1},V_{2},...,V_{k}\}$ of the vertex set $V$ of a graph $G$ into $k$ color classes $V_{i},$ with $i\in\{1,...,k\}$ is called a {\it quorum coloring} if for every vertex $v\in V,$ at least half of the vertices in the closed neighborhood $N[v]$ of $v$ have the same color as $v.$ The maximum cardinali...

Rafik Sahbi, Youcef Belkina, Amar Bennadji · 1 citation
Preprint Oct 2026

The domination number of the $k$-token graph of the complete bipartite graph $K_{m,n}$

This paper is about token graphs and domination number. Let $G=(X,E)$ denote an undirected graph that is connected, with no loops or multiple edges, vertex set $X$, and edge set $E$. Pick a positive integer $k\leq \vert X\vert$. The $k$-token graph of $G$, denoted by $F_k(G)$, is defined as follows. The vertex set $\ma...

Nathaniel Chinman, A. Cortijo, Beatrice Pedroni et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.