# Relation Between Broadcast Domination and Multipacking Numbers on Chordal Graphs

Sandip Das, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee

► To cite this version:

Sandip Das, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee. Relation Between Broadcast Domination and Multipacking Numbers on Chordal Graphs. 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Feb 2023, Gandhinagar, India. pp.297-308, 10.1007/978-3-031-25211-2_23. hal-03974126

HAL Id: hal-03974126

https://hal.science/hal-03974126

Submitted on 5 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Relation between broadcast domination and
multipacking numbers on chordal graphs*

Sandip Das¹, Florent Foucaud²[0000-0001-8198-693X] **, Sk Samim Islam³, and
Joydeep Mukherjee⁴

¹ Indian Statistical Institute, Kolkata, India
[sandip.das69@gmail.com](mailto:sandip.das69@gmail.com)

² Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne,
Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France
[florent.foucaud@uca.fr](mailto:florent.foucaud@uca.fr)

³ Indian Statistical Institute, Kolkata, India
[samimislam08@gmail.com](mailto:samimislam08@gmail.com)

⁴ Ramakrishna Mission Vivekananda Educational and Research Institute, India.
[joydeep.m1981@gmail.com](mailto:joydeep.m1981@gmail.com)

**Abstract.** For a graph $G = (V, E)$ with a vertex set $V$ and an edge set $E$, a function $f: V \to \{0, 1, 2, ..., diam(G)\}$ is called a *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) \le 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 $S \subseteq V$ in a graph $G = (V, E)$ such that for every vertex $v \in V$ and for every integer $r \ge 1$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $S$, that is, there are at most $r$ vertices in $S$ 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 $\text{mp}(G)$.

It is known that $\text{mp}(G) \le \gamma_b(G)$ and that $\gamma_b(G) \le 2\text{mp}(G) + 3$ for any graph $G$, and it was shown that $\gamma_b(G) - \text{mp}(G)$ can be arbitrarily large for connected graphs (as there exist infinitely many connected graphs $G$ where $\gamma_b(G)/\text{mp}(G) = 4/3$ with $\text{mp}(G)$ arbitrarily large). For strongly chordal graphs, it is known that $\text{mp}(G) = \gamma_b(G)$ always holds.

We show that, for any connected chordal graph $G$, $\gamma_b(G) \le \lfloor \frac{3}{2} \text{mp}(G) \rfloor$. We also show that $\gamma_b(G) - \text{mp}(G)$ can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio $\gamma_b(G)/\text{mp}(G) = 10/9$, with $\text{mp}(G)$ arbitrarily large. This result shows that, for chordal graphs, we cannot improve the bound $\gamma_b(G) \le \lfloor \frac{3}{2} \text{mp}(G) \rfloor$ to a bound in the form $\gamma_b(G) \le c_1 \cdot \text{mp}(G) + c_2$, for any constant $c_1 < 10/9$ and $c_2$.

**Keywords:** Chordal graph · Multipacking · Dominating broadcast.

<footnote>* This research was financed by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).</footnote>

<footnote>** Research financed by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR project GRALMECO (ANR-21-CE48-0004).</footnote>
# 1 Introduction

Covering and packing problems are fundamental in graph theory and algorithms [6]. In this paper, we study two dual covering and packing problems called broadcast domination and multipacking. The broadcast domination problem has a natural motivation in telecommunication networks: imagine a network with radio emission towers, where each tower can broadcast information at any radius $r$ for a cost of $r$. The goal is to cover the whole network by minimizing the total cost. The multipacking problem is its natural packing counterpart and generalizes various other standard packing problems. Unlike many standard packing and covering problems, these two problems involve arbitrary distances in graphs, which makes them challenging. The goal of this paper is to study the relation between these two parameters in the class of chordal graphs, which are those graphs that do not contain any induced cycle of a length at least 4.

For a graph $G = (V, E)$ with a vertex set $V$, an edge set $E$ and the diameter $diam(G)$, a function $f: V \to \{0, 1, 2, ..., diam(G)\}$ is called a broadcast on $G$. Suppose $G$ be a graph with a broadcast $f$. Let $d(u, v) = \text{length of a shortest path joining the vertices } u \text{ and } v \text{ in } G$. We say $v \in V$ is a tower of $G$ if $f(v) > 0$. Suppose $u, v \in V$ (possibly, $u = v$) such that $f(v) > 0$ and $d(u, v) \le f(v)$, then we say $v$ broadcasts (or dominates) $u$ and $v$ hears the broadcast from $v$.

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) \le f(v)$, then $f$ is called a dominating broadcast on $G$. The cost of the broadcast $f$ is the quantity $\sigma(f)$, which is the sum of the weights of the broadcasts over all vertices in $G$. So, $\sigma(f) = \sum_{v \in V} f(v)$. The minimum cost of a dominating broadcast in $G$ (taken over all dominating broadcasts) is the broadcast domination number of $G$, denoted by $\gamma_b(G)$. So, $\gamma_b(G) = \min_{f \in D(G)} \sigma(f) = \min_{f \in D(G)} \sum_{v \in V} f(v)$, where $D(G)$ = set of all dominating broadcasts on $G$.

Suppose $f$ is a dominating broadcast with $f(v) \in \{0, 1\} \forall v \in V(G)$, then $\{v \in V(G) : f(v) = 1\}$ is a dominating set on $G$. The minimum cardinality of a dominating set is the domination number which is denoted by $\gamma(G)$.

An optimal broadcast or optimal dominating broadcast on a graph $G$ is a dominating broadcast with a cost equal to $\gamma_b(G)$. A dominating broadcast is efficient if no vertex hears a broadcast from two different vertices. So, no tower can hear a broadcast from another tower in an efficient broadcast. There is a theorem that says, for every graph there is an optimal efficient dominating broadcast [7]. Define a ball of radius $r$ around $v$ by $N_r[v] = \{u \in V(G) : d(v, u) \le r\}$. Suppose $V(G) = \{v_1, v_2, v_3, ..., v_n\}$. Let $c$ and $x$ be the vectors indexed by $(i, k)$ where $v_i \in V(G)$ and $1 \le k \le diam(G)$, with the entries $c_{i,k} = k$ and $x_{i,k} = 1$ when $f(v_i) = k$ and $x_{i,k} = 0$ when $f(v_i) \neq k$. Let $A = [a_{j,(i,k)}]$ be a matrix with the entries

$$a_{j,(i,k)} = \begin{cases} 1 & \text{if } v_j \in N_k[v_i] \\ 0 & \text{otherwise.} \end{cases}$$
Hence, the broadcast domination number can be expressed as an integer linear program:

$$ \gamma_b(G) = \min\{c.x : Ax \ge \mathbf{1}, x_{i,k} \in \{0,1\}\}. $$

The maximum multipacking problem is the dual integer program of the above problem. Moreover, multipacking is a generalization of packing problems. A multipacking is a set $M \subseteq V$ in a graph $G = (V, E)$ such that $|N_r[v] \cap M| \le r$ for each vertex $v \in V(G)$ and for every integer $r \ge 1$. The multipacking number of $G$ is the maximum cardinality of a multipacking of $G$ and it is denoted by $mp(G)$. A maximum multipacking is a multipacking $M$ of a graph $G$ such that $|M| = mp(G)$. If $M$ is a multipacking, we define a vector $y$ with the entries $y_j = 1$ when $v_j \in M$ and $y_j = 0$ when $v_j \notin M$. So,

$$ mp(G) = \max\{y.\mathbf{1} : yA \le c, y_j \in \{0,1\}\}. $$

Broadcast domination is a generalization of domination problems and multipacking is a generalization of packing problems. Erwin [8, 9] introduced broadcast domination in his doctoral thesis in 2001. Multipacking was introduced in Teshima's Master's Thesis [15] in 2012 (also see [3, 6, 7, 14]). For general graphs, an optimal dominating broadcast can be found in polynomial-time $O(n^6)$ [12]. The same problem can be solved in linear time for trees [4]. However, until now, there is no known polynomial-time algorithm to find a maximum multipacking of general graphs (the problem is also not known to be NP-hard). However, polynomial-time algorithms are known for trees and more generally, strongly chordal graphs [4]. See [10] for other references concerning algorithmic results on the two problems.

It is known that $mp(G) \le \gamma_b(G)$, since broadcast domination and multipacking are dual problems [5]. It is known that $\gamma_b(G) \le 2mp(G) + 3$ [1] and it is a conjecture that $\gamma_b(G) \le 2mp(G)$ for every graph $G$ [1]. Hartnell and Mynhardt [11] constructed a family of connected graphs such that the difference $\gamma_b(G) - mp(G)$ can be arbitrarily large and in fact, for which the ratio $\gamma_b(G)/mp(G) = 4/3$. Therefore, for general connected graphs,

$$ \frac{4}{3} \le \lim_{mp(G) \to \infty} \sup \left\{ \frac{\gamma_b(G)}{mp(G)} \right\} \le 2. $$

A natural question comes to mind: What is the optimal bound on this ratio for other graph classes? It is known that $\gamma_b(G) = mp(G)$ holds for strongly chordal graphs [4]. Thus, a natural class to study is the class of chordal graphs.

In this paper, we establish an improved relation between $\gamma_b(G)$ and $mp(G)$ for connected chordal graphs by showing that $\gamma_b(G) \le \lceil \frac{3}{2}mp(G) \rceil$. We then construct a family of connected chordal graphs such that the difference $\gamma_b(G) - mp(G)$ can be arbitrarily large and the ratio $\gamma_b(G)/mp(G) = 10/9$ for every member $G$ of that family. Thus, for chordal connected graphs $G$, we have:

$$ \frac{10}{9} \le \lim_{mp(G) \to \infty} \sup \left\{ \frac{\gamma_b(G)}{mp(G)} \right\} \le \frac{3}{2}. $$
We also make a connection with the fractional versions of the two concepts,
as introduced in [2].

In Section 2, we show that for any connected chordal graph $G$, $\gamma_b(G) \le \lfloor \frac{3}{2} \text{mp}(G) \rfloor$ and there is a polynomial-time algorithm to construct a multipacking of $G$ of size at least $\lfloor \frac{2\text{mp}(G)-1}{3} \rfloor$. In Section 3, we prove our main result which says that the difference $\gamma_b(G) - \text{mp}(G)$ can be arbitrarily large for connected chordal graphs, and we conclude in Section 4.

## 2 An inequality linking Broadcast domination and Multipacking numbers of Chordal Graphs

In this section, we use results from the literature to show that the general bound connecting multipacking number and broadcast domination number can be improved for chordal graphs.

**Theorem 1 ([11]).** If $G$ is a connected graph of order at least 2 having diameter $d$ and multipacking number $\text{mp}(G)$, where $P = v_0, \dots, v_d$ is a diametral path of $G$, then the set $M = \{v_i : i \equiv 0 (\text{mod } 3), i = 0, 1, \dots, d\}$ is a multipacking of $G$ of size $\lfloor \frac{d+1}{3} \rfloor$ and $\lfloor \frac{d+1}{3} \rfloor \le \text{mp}(G)$.

**Theorem 2 ([9, 15]).** If $G$ is a connected graph of order at least 2 having radius $r$, diameter $d$, multipacking number $\text{mp}(G)$, broadcast domination number $\gamma_b(G)$ and domination number $\gamma(G)$, then $\text{mp}(G) \le \gamma_b(G) \le \min\{\gamma(G), r\}$.

**Theorem 3 ([13]).** If $G$ is a connected chordal graph with radius $r$ and diameter $d$, then $2r \le d + 2$.

**Proposition 1.** If $G$ is a connected chordal graph, then $\gamma_b(G) \le \lfloor \frac{3}{2} \text{mp}(G) \rfloor$.

*Proof.* From Theorem 1, $\lfloor \frac{d+1}{3} \rfloor \le \text{mp}(G)$ which implies that $d \le 3\text{mp}(G) - 1$. Moreover, from Theorem 2 and Theorem 3, $\gamma_b(G) \le r \le \lfloor \frac{d+2}{2} \rfloor \le \lfloor \frac{(3\text{mp}(G)-1)+2}{2} \rfloor = \lfloor \frac{3}{2} \text{mp}(G) + \frac{1}{2} \rfloor$. Therefore, $\gamma_b(G) \le \lfloor \frac{3}{2} \text{mp}(G) + \frac{1}{2} \rfloor = \lfloor \frac{3}{2} \text{mp}(G) \rfloor$. $\square$

The proof of Proposition 1 has the following algorithmic application.

**Proposition 2.** If $G$ is a connected chordal graph, there is a polynomial-time algorithm to construct a multipacking of $G$ of size at least $\lfloor \frac{2\text{mp}(G)-1}{3} \rfloor$.

*Proof.* If $P = v_0, \dots, v_d$ is a diametral path of $G$, then the set $M = \{v_i : i \equiv 0 (\text{mod } 3), i = 0, 1, \dots, d\}$ is a multipacking of $G$ of size $\lfloor \frac{d+1}{3} \rfloor$ by Theorem 1. We can construct $M$ in polynomial-time since we can find a diametral path of a graph $G$ in polynomial-time. Moreover, from Theorem 1, Theorem 2 and Theorem 3, $\lfloor \frac{2\text{mp}(G)-1}{3} \rfloor \le \lfloor \frac{2r-1}{3} \rfloor \le \lfloor \frac{d+1}{3} \rfloor \le \text{mp}(G)$. $\square$

**Example 1** The connected chordal graph $S_3$ (Fig. 1) has $\text{mp}(S_3) = 1$ and $\gamma_b(S_3) = 2$. So, here $\gamma_b(S_3) = \lfloor \frac{3}{2} \text{mp}(S_3) \rfloor$.
<figure><img src="image_2.png" /><figcaption>Fig. 1: $S_3$ is a connected chordal graph with $\gamma_b(S_3) = 2$ and $\text{mp}(S_3) = 1$</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: $F$ is a connected chordal graph with $\gamma_b(F) = 3$ and $\text{mp}(F) = 2$</figcaption></figure>

**Example 2** The connected chordal graph $F$ (Fig. 2) has $\text{mp}(F) = 2$ and $\gamma_b(F) = 3$. So, here $\gamma_b(F) = \lceil \frac{3}{2} \text{mp}(F) \rceil$.

**Example 3** The connected chordal graph $H$ (Fig. 3) has $\text{mp}(H) = 4$ and $\gamma_b(H) = 6$. So, here $\gamma_b(H) = \lceil \frac{3}{2} \text{mp}(H) \rceil$.

We could not find an example of connected chordal graph with $\text{mp}(G) = 3$ and $\gamma_b(G) = \lceil \frac{3}{2} \text{mp}(G) \rceil = 5$.

### 3 Unboundedness of the gap between Broadcast domination and Multipacking numbers of Chordal graphs

Here we prove that the difference between broadcast domination number and multipacking number of connected chordal graphs can be arbitrarily large. We state the theorem formally below.

**Theorem 4.** The difference $\gamma_b(G) - \text{mp}(G)$ can be arbitrarily large for connected chordal graphs.

Consider the graph $G_1$ as in Fig. 4. Let $B_1$ and $B_2$ be two isomorphic copies of $G_1$. Join $b_{1,21}$ of $B_1$ and $b_{2,1}$ of $B_2$ by an edge (Fig. 5 and 6). We denote this new graph by $G_2$ (Fig. 5). In this way, we form $G_k$ by joining $k$ isomorphic copies of $G_1$: $B_1, B_2, \dots, B_k$ (Fig. 6). Here $B_i$ is joined with $B_{i+1}$ by joining $b_{i,21}$ and $b_{i+1,1}$.
<figure><img src="image_4.png" /><figcaption>Fig. 3: $H$ is a connected chordal graph with $\gamma_b(H) = 6$ and $\mathrm{mp}(H) = 4$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: $G_1$ is a connected chordal graph with $\gamma_b(G_1) = 5$ and $\mathrm{mp}(G_1) = 5$. $M_1 = \{m_i : 1 \le i \le 5\}$ is a multipacking of size 5.</figcaption></figure>

We say that $B_i$ is the $i$-th block of $G_k$. $B_i$ is an induced subgraph of $G_k$ as given by $B_i = G_k[\{b_{i,j} : 1 \le j \le 21\}]$. Similarly, for $1 \le i \le 2k-1$, we define $B_i \cup B_{i+1}$, induced subgraph of $G_{2k}$, as $B_i \cup B_{i+1} = G_{2k}[\{b_{i,j}, b_{i+1,j} : 1 \le j \le 21\}]$. We prove Theorem 4 by establishing that $\gamma_b(G_{2k}) = 10k$ and $\mathrm{mp}(G_{2k}) = 9k$. Then we can say, for all natural numbers $k$, $\gamma_b(G_{2k}) - \mathrm{mp}(G_{2k}) = k$, so the difference can be arbitrarily large.

**3.1 Proof of Theorem 4**

Our proof of Theorem 4 is accomplished through a set of lemmas which are stated and proved below. We begin by observing a basic fact about multipacking in a graph. We formally state it in Lemma 1 for ease of future reference.

**Lemma 1.** Suppose $M$ is a multipacking in a graph $G$. If $u, v \in M$ and $u \ne v$, then $d(u, v) \ge 3$.

*Proof.* If $d(u, v) = 1$, then $u, v \in N_1[v] \cap M$, then $M$ cannot be a multipacking. So, $d(u, v) \ne 1$. If $d(u, v) = 2$, then there exists a common neighbour $w$ of $u$ and $v$. So, $u, v \in N_1[w] \cap M$, then $M$ cannot be a multipacking. So, $d(u, v) \ne 2$. Therefore, $d(u, v) > 2$. $\square$

**Lemma 2.** $\mathrm{mp}(G_{2k}) \ge 9k$, for each positive integer $k$.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Graph $G_2$ with $\gamma_b(G_2) = 10$ and $\mathrm{mp}(G_2) = 9$. $M = \{m_i : 1 \le i \le 9\}$ is a multipacking of size 9.</figcaption></figure>

**Proof.** Consider the set $M_{2k} = \{b_{2i-1,1}, b_{2i-1,7}, b_{2i-1,13}, b_{2i-1,18}, b_{2i-1,21}, b_{2i,4}, b_{2i,8}, b_{2i,14}, b_{2i,18} : 1 \le i \le k\}$ (Fig. 6) of size $9k$. We want to show that $M_{2k}$ is a multipacking of $G_{2k}$. So, we have to prove that, $|N_r[v] \cap M_{2k}| \le r$ for each vertex $v \in V(G_{2k})$ and for every integer $r \ge 1$. We prove this statement using induction on $r$. It can be checked that $|N_r[v] \cap M_{2k}| \le r$ for each vertex $v \in V(G_{2k})$ and for each $r \in \{1, 2, 3, 4\}$. Now assume that the statement is true for $r = s$, we want to prove that, it is true for $r = s+4$. Observe that, $|(N_{s+4}[v] \setminus N_s[v]) \cap M_{2k}| \le 4$ for every vertex $v \in V(G_{2k})$. Therefore, $|N_{s+4}[v] \cap M_{2k}| \le |N_s[v] \cap M_{2k}| + 4 \le s + 4$. So, the statement is true. Therefore, $M_{2k}$ is a multipacking of $G_{2k}$. So, $\mathrm{mp}(G_{2k}) \ge |M_{2k}| = 9k$. $\square$

**Lemma 3.** $\mathrm{mp}(G_1) = 5$.

**Proof.** $V(G_1) = N_3[b_{1,7}] \cup N_2[b_{1,17}]$. Suppose $M$ is a multipacking on $G_1$ such that $|M| = \mathrm{mp}(G_1)$. So, $|M \cap N_3[b_{1,7}]| \le 3$ and $|M \cap N_2[b_{1,17}]| \le 2$. Therefore, $|M \cap (N_3[b_{1,7}] \cup N_2[b_{1,17}])| \le 5$. So, $|M \cap V(G)| \le 5$, that implies $|M| \le 5$. Let $M_1 = \{b_{1,1}, b_{1,7}, b_{1,13}, b_{1,18}, b_{1,21}\}$. Since $|N_r[v] \cap M| \le r$ for each vertex $v \in V(G_1)$ and for every integer $r \ge 1$, so $M_1$ is a multipacking of size 5. Then $5 = |M_1| \le |M|$. So, $|M| = 5$. Therefore, $\mathrm{mp}(G_1) = 5$. $\square$

So, now we have $\mathrm{mp}(G_1) = 5$. Using this fact we prove that $\mathrm{mp}(G_2) = 9$.

**Lemma 4.** $\mathrm{mp}(G_2) = 9$.

**Proof.** As mentioned before, $B_i = G_k[\{b_{i,j} : 1 \le j \le 21\}]$, $1 \le i \le 2$. So, $B_1$ and $B_2$ are two blocks in $G_2$ which are isomorphic to $G_1$. Let $M$ be a multipacking
<figure><img src="image_7.png" /><figcaption>Fig. 6</figcaption></figure>

of $G_2$ with size $\text{mp}(G_2)$. So, $|M| \ge 9$ by Lemma 2. Since $M$ is a multipacking of $G_2$, so $M \cap V(B_1)$ and $M \cap V(B_2)$ are multipackings of $B_1$ and $B_2$, respectively. Let $M \cap V(B_1) = M_1$ and $M \cap V(B_2) = M_2$. Since $B_1 \cong G_1$ and $B_2 \cong G_1$, so $\text{mp}(B_1) = 5$ and $\text{mp}(B_2) = 5$ by Lemma 3. This implies $|M_1| \le 5$ and $|M_2| \le 5$. Since $V(B_1) \cup V(B_2) = V(G_2)$ and $V(B_1) \cap V(B_2) = \emptyset$, so $M_1 \cap M_2 = \emptyset$ and $|M| = |M_1| + |M_2|$. Therefore, $9 \le |M| = |M_1| + |M_2| \le 10$. So, $9 \le |M| \le 10$.

We establish this lemma by using contradiction on $|M|$. In the first step, we prove that if $|M_1| = 5$, then the particular vertex $b_{1,21} \in M_1$. Using this, we can show that $|M_2| \le 4$. In this way we show that $|M| \le 9$.

For the purpose of contradiction, we assume that $|M| = 10$. So, $|M_1| + |M_2| = 10$, and also $|M_1| \le 5$, $|M_2| \le 5$. Therefore, $|M_1| = |M_2| = 5$.

**Claim 4.1.** If $|M_1| = 5$, then $b_{1,21} \in M_1$.

*Proof of claim.* Suppose $b_{1,21} \notin M$. Let $S = \{b_{1,7}, b_{1,14}\}$, $S_1 = \{b_{1,r} : 1 \le r \le 6\}$, $S_2 = \{b_{1,r} : 8 \le r \le 13\}$, $S_3 = \{b_{1,r} : 15 \le r \le 20\}$. If $u, v \in S_t$, then
$d(u, v) \le 2$, this holds for each $t \in \{1, 2, 3\}$. So, by Lemma 1, $u, v$ together cannot be in a multipacking. Therefore $|S_t \cap M_1| \le 1$ for $t = 1, 2, 3$ and $|S \cap M_1| \le |S| = 2$. Now, $5 = |M_1| = |M_1 \cap [V(G_1) \setminus \{b_{1,21}\}| = |M_1 \cap (S \cup S_1 \cup S_2 \cup S_3)| = |(M_1 \cap S) \cup (M_1 \cap S_1) \cup (M_1 \cap S_2) \cup (M_1 \cap S_3)| \le |M_1 \cap S| + |M_1 \cap S_1| + |M_1 \cap S_2| + |M_1 \cap S_3| \le 2 + 1 + 1 + 1 = 5$. Therefore, $|S_t \cap M_1| = 1$ for $t = 1, 2, 3$ and $|S \cap M_1| = 2$, so $b_{1,7}, b_{1,14} \in M_1$. Since $|S_2 \cap M_1| = 1$, there exists $w \in S_2 \cap M_1$. Then $N_2[b_{1,10}]$ contains three vertices $b_{1,7}, b_{1,14}, w$ of $M_1$, which is not possible. So, this is a contradiction. Therefore, $b_{1,21} \in M_1$. ▲

**Claim 4.2.** If $|M_1| = 5$, then $|M_2| \le 4$.

*Proof of claim.* Let $S' = \{b_{2,14}, b_{2,21}\}$, $S_4 = \{b_{2,r} : 1 \le r \le 6\}$, $S_5 = \{b_{2,r} : 8 \le r \le 13\}$, $S_6 = \{b_{2,r} : 15 \le r \le 20\}$. By Lemma 1, $|S_t \cap M_2| \le 1$ for $t = 4, 5, 6$ and also $|S' \cap M_2| \le |S'| = 2$.

Observe that, if $S_4 \cap M_2 \ne \emptyset$, then $b_{2,7} \notin M_2$ (i.e. if $b_{2,7} \in M_2$, then $S_4 \cap M_2 = \emptyset$). [Suppose not, then $S_4 \cap M_2 \ne \emptyset$ and $b_{2,7} \in M_2$, so, there exists $u \in S_4 \cap M_2$. Then $N_2[b_{2,3}]$ contains three vertices $b_{1,21}, b_{2,7}, u$ of $M$, which is not possible. This is a contradiction].

Suppose $S_4 \cap M_2 \ne \emptyset$, then $b_{2,7} \notin M_2$. Now, $5 = |M_2| = |M_2 \cap [V(B_2) \setminus \{b_{2,7}\}| = |M_2 \cap (S' \cup S_4 \cup S_5 \cup S_6)| = |(M_2 \cap S') \cup (M_2 \cap S_4) \cup (M_2 \cap S_5) \cup (M_2 \cap S_6)| \le |M_2 \cap S'| + |M_2 \cap S_4| + |M_2 \cap S_5| + |M_2 \cap S_6| \le 2 + 1 + 1 + 1 = 5$. Therefore $|S_t \cap M_2| = 1$ for $t = 4, 5, 6$ and $|S' \cap M_2| = 2$. Since $|M_2 \cap S_6| = 1$, so there exists $u_1 \in M_2 \cap S_6$. Then $N_2[b_{2,17}]$ contains three vertices $b_{2,14}, b_{2,21}, u_1$ of $M_2$, which is not possible. So, this is a contradiction.

Suppose $S_4 \cap M_2 = \emptyset$, then either $b_{2,7} \in M_2$ or $b_{2,7} \notin M_2$. First consider $b_{2,7} \notin M_2$, then $5 = |M_2| = |M_2 \cap (S' \cup S_5 \cup S_6)| = |(M_2 \cap S') \cup (M_2 \cap S_5) \cup (M_2 \cap S_6)| \le |M_2 \cap S'| + |M_2 \cap S_5| + |M_2 \cap S_6| \le 2 + 1 + 1 = 4$. So, this is a contradiction. And if $b_{2,7} \in M_2$, then $5 = |M_2| = |M_2 \cap (S' \cup S_5 \cup S_6 \cup \{b_{2,7}\})| = |(M_2 \cap S') \cup (M_2 \cap S_5) \cup (M_2 \cap S_6) \cup (M_2 \cap \{b_{2,7}\})| \le |M_2 \cap S'| + |M_2 \cap S_5| + |M_2 \cap S_6| + |M_2 \cap \{b_{2,7}\}| \le 2 + 1 + 1 + 1 = 5$. Therefore $|S_t \cap M_2| = 1$ for $t = 5, 6$ and $|S' \cap M_2| = 2$. Since $|M_2 \cap S_6| = 1$, so there exists $u_2 \in M_2 \cap S_6$. Then $N_2[b_{2,17}]$ contains three vertices $b_{2,14}, b_{2,21}, u_2$ of $M_2$, which is not possible. So, this is a contradiction. So, $|M_1| = 5 \implies |M_2| \le 4$. ▲

Recall that for contradiction, we assume $|M| = 10$, which implies $|M_2| = 5$. In the proof of the above claim, we established $|M_2| \le 4$, which in turn contradicts our assumption. So, $|M| \ne 10$. Therefore, $|M| = 9$. □

Notice that graph $G_{2k}$ has $k$ copies of $G_2$. Moreover, we have $\text{mp}(G_2) = 9$. If $\text{mp}(G_{2k}) > 9k$, then we will use the Pigeonhole principle to show that $\text{mp}(G_{2k}) = 9k$.

**Lemma 5.** $\text{mp}(G_{2k}) = 9k$, for each positive integer $k$.

*Proof.* For $k = 1$ it is true by Lemma 4. Moreover, we know $\text{mp}(G_{2k}) \ge 9k$ by Lemma 2. Suppose $k > 1$ and assume $\text{mp}(G_{2k}) > 9k$. Let $\hat{M}$ be a multipacking of $G_{2k}$ such that $|\hat{M}| > 9k$. Let $\hat{B}_j$ be a subgraph of $G_{2k}$ defined as $\hat{B}_j = B_{2j-1} \cup B_{2j}$ where $1 \le j \le k$. So, $V(G_{2k}) = \cup_{j=1}^k V(\hat{B}_j)$ and $V(\hat{B}_p) \cap V(\hat{B}_q) = \emptyset$ for all
$p \neq q$ and $p, q \in \{1, 2, 3, \dots, k\}$. Since $|\hat{M}| > 9k$, so by the Pigeonhole principle there exists a number $j \in \{1, 2, 3, \dots, k\}$ such that $|\hat{M} \cap \hat{B}_j| > 9$. Since $\hat{M} \cap \hat{B}_j$ is a multipacking of $\hat{B}_j$, so $\mathrm{mp}(\hat{B}_j) > 9$. But $\hat{B}_j \cong G_2$ and $\mathrm{mp}(G_2) = 9$ by Lemma 4, so $\mathrm{mp}(\hat{B}_j) = 9$, which is a contradiction. Therefore, $\mathrm{mp}(G_{2k}) = 9k$. $\square$

R. C. Brewster and L. Duchesne [2] introduced fractional multipacking in 2013 (also see [16]). Suppose $G$ is a graph with $V(G) = \{v_1, v_2, v_3, \dots, v_n\}$ and $w: V(G) \to [0, \infty)$ is a function. So, $w(v)$ is a weight on a vertex $v \in V(G)$. Let $w(S) = \sum_{u \in S} w(u)$ where $S \subseteq V(G)$. We say $w$ is a fractional multipacking of $G$, if $w(N_r[v]) \le r$ for each vertex $v \in V(G)$ and for every integer $r \ge 1$. The fractional multipacking number of $G$ is the value $\max_w w(V(G))$ where $w$ is any fractional multipacking and it is denoted by $mp_f(G)$. A maximum fractional multipacking is a fractional multipacking $w$ of a graph $G$ such that $w(V(G)) = mp_f(G)$. If $w$ is a fractional multipacking, we define a vector $y$ with the entries $y_j = w(v_j)$. So,

$$mp_f(G) = \max\{y.1 : yA \le c, y_j \ge 0\}.$$

So, this is a linear program which is the dual of the linear program $\min\{c.x : Ax \ge 1, x_{i,k} \ge 0\}$. Let,

$$\gamma_{b,f}(G) = \min\{c.x : Ax \ge 1, x_{i,k} \ge 0\}.$$

Using the strong duality theorem for linear programming, we can say that

$$\mathrm{mp}(G) \le \mathrm{mp}_f(G) = \gamma_{b,f}(G) \le \gamma_b(G).$$

**Lemma 6.** If $k$ is a positive integer, then $mp_f(G_k) \ge 5k$.

*Proof.* We define a function $w: V(G_k) \to [0, \infty)$ where $w(b_{i,1}) = w(b_{i,6}) = w(b_{i,7}) = w(b_{i,8}) = w(b_{i,13}) = w(b_{i,14}) = w(b_{i,15}) = w(b_{i,20}) = w(b_{i,21}) = \frac{1}{3}$ and $w(b_{i,4}) = w(b_{i,11}) = w(b_{i,18}) = \frac{2}{3}$ for each $i \in \{1, 2, 3, \dots, k\}$ (Fig. 7). So, $w(G_k) = 5k$. We want to show that $w$ is a fractional multipacking of $G_k$. So, we have to prove that $w(N_r[v]) \le r$ for each vertex $v \in V(G_k)$ and for every integer $r \ge 1$. We prove this statement using induction on $r$. It can be checked that $w(N_r[v]) \le r$ for each vertex $v \in V(G_k)$ and for each $r \in \{1, 2, 3, 4\}$. Now assume that the statement is true for $r = s$, we want to prove that it is true for $r = s + 4$. Observe that, $w(N_{s+4}[v] \setminus N_s[v]) \le 4$, $\forall v \in V(G_k)$. Therefore, $w(N_{s+4}[v]) \le w(N_s[v]) + 4 \le s + 4$. So, the statement is true. So, $w$ is a fractional multipacking of $G_k$. Therefore, $mp_f(G_k) \ge 5k$. $\square$

**Lemma 7.** If $k$ is a positive integer, then $mp_f(G_k) = \gamma_b(G_k) = 5k$.

*Proof.* Define a broadcast $f$ on $G_k$ as $f(b_{i,j}) = \begin{cases} 2 & \text{if } 1 \le i \le k \text{ and } j = 6, 17 \\ 1 & \text{if } 1 \le i \le k \text{ and } j = 12 \\ 0 & \text{otherwise} \end{cases}$.

Here $f$ is an efficient dominating broadcast and $\sum_{v \in V(G_k)} f(v) = 5k$. So, $\gamma_b(G_k) \le 5k, \forall k \in \mathbb{N}$. So, by the strong duality theorem and Lemma 6, $5k \le mp_f(G_k) = \gamma_{b,f}(G_k) \le \gamma_b(G_k) \le 5k$. Therefore, $mp_f(G_k) = \gamma_b(G_k) = 5k$. $\square$
<figure><img src="image_8.png" /><figcaption>Fig. 7</figcaption></figure>

So, $\gamma_b(G_{2k}) = 10k$ by Lemma 7 and $\mathrm{mp}(G_{2k}) = 9k$ by Lemma 5. So, we can say that for all positive integers $k$, $\gamma_b(G_{2k}) - \mathrm{mp}(G_{2k}) = k$. Therefore, this proves Theorem 4. So, the difference $\gamma_b(G) - \mathrm{mp}(G)$ can be arbitrarily large for connected chordal graphs.

**Corollary 1.** The difference $mp_f(G) - \mathrm{mp}(G)$ can be arbitrarily large for connected chordal graphs.

*Proof.* We get $mp_f(G_{2k}) = 10k$ by Lemma 7 and $\mathrm{mp}(G_{2k}) = 9k$ by Lemma 5. Therefore, $mp_f(G_{2k}) - \mathrm{mp}(G_{2k}) = k$ for all positive integers $k$. $\square$

**Corollary 2.** For every integer $k \ge 1$, there is a connected chordal graph $G_{2k}$ with $\mathrm{mp}(G_{2k}) = 9k$, $mp_f(G_{2k})/\mathrm{mp}(G_{2k}) = 10/9$ and $\gamma_b(G_{2k})/\mathrm{mp}(G_{2k}) = 10/9$.

**Corollary 3.** For connected chordal graphs $G$,

$$ \frac{10}{9} \le \lim_{\mathrm{mp}(G) \to \infty} \sup \left\{ \frac{\gamma_b(G)}{\mathrm{mp}(G)} \right\} \le \frac{3}{2}. $$
# 4 Conclusion

We have shown that the bound $\gamma_b(G) \le 2\text{mp}(G) + 3$ for general graphs $G$ can be improved to $\gamma_b(G) \le \lfloor \frac{3}{2}\text{mp}(G) \rfloor$ for connected chordal graphs. It is known that for strongly chordal graphs, $\gamma_b(G) = \text{mp}(G)$, we have shown that this is not the case for connected chordal graphs. Even more, $\gamma_b(G) - \text{mp}(G)$ can be arbitrarily large for connected chordal graphs, as we have constructed infinitely many connected chordal graphs $G$ where $\gamma_b(G)/\text{mp}(G) = 10/9$ and $\text{mp}(G)$ is arbitrarily large.

It remains an interesting open problem to determine the best possible value of $\lim_{\text{mp}(G) \to \infty} \sup \left\{ \frac{\gamma_b(G)}{\text{mp}(G)} \right\}$ for general connected graphs and for chordal connected graphs. This problem could also be studied for other interesting graph classes.

# References

1. Beaudou, L., Brewster, R.C., Foucaud, F.: Broadcast domination and multipacking: bounds and the integrality gap. The Australasian Journal of Combinatorics **74**(1), 86–97 (2019)

2. Brewster, R., Duchesne, L.: Broadcast domination and fractional multipackings. manuscript (2013)

3. Brewster, R.C., Beaudou, L.: On the multipacking number of grid graphs. Discrete Mathematics & Theoretical Computer Science **21** (2019)

4. Brewster, R.C., MacGillivray, G., Yang, F.: Broadcast domination and multipacking in strongly chordal graphs. Discrete Applied Mathematics **261**, 108–118 (2019)

5. Brewster, R.C., Mynhardt, C.M., Teshima, L.E.: New bounds for the broadcast domination number of a graph. Central European Journal of Mathematics **11**(7), 1334–1343 (2013)

6. Cornuéjols, G.: Combinatorial optimization: Packing and covering. SIAM (2001)

7. Dunbar, J.E., Erwin, D.J., Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T.: Broadcasts in graphs. Discrete Applied Mathematics **154**(1), 59–75 (2006)

8. Erwin, D.J.: Dominating broadcasts in graphs. Bull. Inst. Combin. Appl **42**(89), 105 (2004)

9. Erwin, D.J.: Cost domination in graphs. PhD Thesis, Western Michigan University (2001)

10. Foucaud, F., Gras, B., Perez, A., Sikora, F.: On the complexity of broadcast domination and multipacking in digraphs. Algorithmica **83**(9), 2651–2677 (2021)

11. Hartnell, B.L., Mynhardt, C.M.: On the difference between broadcast and multipacking numbers of graphs. Utilitas Mathematica **94**, 19–29 (2014)

12. Heggernes, P., Lokshtanov, D.: Optimal broadcast domination in polynomial time. Discrete Mathematics **306**(24), 3267–3280 (2006)

13. Laskar, R., Shier, D.: On powers and centers of chordal graphs. Discrete Applied Mathematics **6**(2), 139–147 (1983)

14. Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics **61**(1), 225–233 (1975)

15. Teshima, L.E.: Broadcasts and multipackings in graphs. Ph.D. thesis (2012)

16. Teshima, L.E.: Multipackings in graphs. arXiv preprint arXiv:1409.8057 (2014)