For an undirected graph , a dominating broadcast on is a function : () → N such that for any vertex ∈ (), there exists a vertex ∈ () with () ⩾ 1 and (, ) ⩽ (). The cost of is ∑︀∈ (). The minimum cost over all the dominating broadcasts on is defined as the broadcast domination number () of . A multipacking in is a subset ⊆ () such that, for every vertex ∈ () and every positive integer , the number of vertices in within distance of is at most . The multipacking number of , denoted mp(), is the maximum cardinality of a multipacking in . These two optimisation problems are duals of each other, and it easily follows that mp() ⩽ (). It is known that () ⩽ 2 mp() + 3 and conjectured that () ⩽ 2 mp(). In this paper, we show that for the -dimensional hypercube Since () = − 1 for all ⩾ 3, this verifies the above conjecture on hypercubes and, more interestingly, gives a sequence of connected graphs for which the ratio mp(()) approaches 2, a search for which was initiated by Beaudou, Brewster and Foucaud in 2019. It follows that, for connected graphs
⌊︁ ⌋︁ 2
+ 6√2.
⩽ mp() ⩽ 2 mlpim(s)→up∞ ︂{ mp(()) }︂ = 2.
The lower bound on mp() is established by a recursive construction, and the upper bound is established using a classic result from discrepancy theory.
A dominating set in an undirected graph is a set ⊆ () such that every node in is either in or adjacent to a node in . One of the many motivations to study dominating sets and its variants comes from optimising the placement of facilities on the nodes of a network so that services can be easily distributed to every node in the network. In particular, if placing a facility at a node serves that node and all its neighbours, and the cost of establishing a facility is the same across all the nodes, then the best strategy is to identify a smallest dominating set of the graph and place one facility on each node of this set. Suppose we can set up facilities that can serve a larger range, even at a larger cost, then we might be able to do a better distribution than the above strategy. In particular, if the cost of setting up a facility is proportional to the distance up to which it can serve, then the task becomes that of finding a dominating broadcast of minimum cost as defined next.
Definition 1.1. A broadcast on a graph = (, ) is a function : → N. The cost of a broadcast is ∑︀∈ (). A broadcast is said to be dominating if every vertex of lies within a distance () of some vertex ∈ with () ⩾ 1. The broadcast domination number, denoted (), is the minimum cost over all dominating broadcasts on .
Trees of radius 2 give an example of a family of graphs where () (the size of a smallest dominating
set in ) is unbounded but () is at most 2. The notion of broadcast domination was introduced by
Erwin [
Definition 1.2. For a graph = (, ), a set ⊆ is a multipacking in if for every vertex ∈ , |[] ∩ | ⩽ for all ⩾ 1. The multipacking number mp() is the maximum cardinality of a multipacking in .
From the LP duality, we get that mp() ⩽ () for every graph . On the other hand, Hartnell and
Mynhardt [
Conjecture 1.3. [
The reason for the multiplier of 2 in the above conjecture is that there are a few small graphs
(including 4 and 5, cycles on 4 and 5 vertices) where mp() = 1 and () = 2 and a few others
where mp() = 2 and () = 4. By taking disjoint copies of these examples, one can construct, for
any ⩾ 1, a graph with mp() = and () = 2. Hence, the above conjecture, if true, is tight.
While noting this, Beaudou et al. [
The main contribution of this note is to show that hypercubes form an infinite family of connected graphs where mp(()) approaches 2. An -dimensional hypercube is the Cartesian product of copies of the complete graph 2. Alternatively, it can be visualized as a graph whose vertex set is {0, 1} and two vertices are adjacent if exactly one coordinate is diferent. Our main result is
Brešar and Špacapan [
lim sup mp()→∞ ︂{ () }︂ mp() = 2.
While our Corollary 1.5 improves the above, optimal bounds for this ratio were studied for special graph
classes. For connected chordal graphs , Das et al. [
The lower bound in Theorem 1.4 is proved by introducing a recursive technique that systematically
generates multipacking of higher-dimensional hypercubes by combining multipackings from lower
dimensions. For the proof of the upper bound, we bank on a classic result by Spencer [
The first inequality in mp() ⩽ () ⩽ 2 mp() + 3 was shown to be tight in some graph families
like trees [
Hartnell and Mynhardt [
Every graph discussed in this note is finite, simple, and undirected. N denotes the set of natural numbers
(including 0). For any positive integer , we denote the set {1, 2, . . . , } as []. Any undefined terms
and notations are in accordance with Chartrand et al. [
We use exponential notation to indicate repeated sequences in the vertex so that a vertex 110001 in 6 will be written as 12031. The hamming weight wt() of a vertex is the distance of from 0 in . As a warm-up, first we determine mp() for ⩽ 6. It is easy to observe that mp(1) = 1, mp(2) = 1, mp(3) = 2, mp(4) = 2 and mp(5) = 2.
Proposition 2.1. mp(6) = 4.
Proof. One can observe that, since the set {06, 0313, 1303, 16} is a multipacking in 6, mp(6) ⩾ 4. Now, we show that no set of order 5 can be a multipacking in 6. On the contrary, let be a multipacking in of 5 vertices. As is vertex-transitive, without loss of generality, suppose 06 ∈ . Then cannot contain any vertex of hamming weight 1 or 2. Then ∖ {06} ⊆ 3[16]. Hence, |3[16] ∩ | = 4 > 3, a contradiction to the fact that is a multipacking. Therefore, mp(6) = 4.
Since +1 contains a copy of as a distance preserving subgraph, it is easy to observe that the multipacking number of is monotonic in .
Observation 2.2. For any positive integer , mp() ⩽ mp(+1).
We begin with a couple of lemmas needed for the recursive construction. Given a vertex ∈ , and an integer ⩾ 1, we define · as the binary string obtained by concatenating to , where ∈ {0, 1}. For any set of vertices ,
· = { · : ∈ }.
Lemma 2.3. Let 0 ⩾ 1 be two positive integers, and 0 and 1 be two hypercubes equipped with multipackings 0 and 1, respectively. Further, let and be the set Then is a multipacking in .
= 0 + max(|0|, 2) + max(|1|, 2) − 1,
(0− 0 · 0) ∪ (1− 1 · 1).
Proof. Let = | | = |0| + |1|. Pick any ∈ () and any ∈ [ − 1]. We will show that the number of vertices of in [] is at most by counting separately the number of vertices of 0− 0 · 0 and 1− 1 · 1 in [].
Let 0 denote the 0-length sufix of (the last 0 bits) and 1 denote the 1-length sufix of . Let 0 and 1 respectively denote the number of zeros and ones in the first ( − 0) bits of . For any vertex ∈ 0, (, 0− 0 · ) = 1 + 0 (0, ). For any vertex ∈ 1, (, 1− 1 · ) ⩾ 0 + 1 (1, ). Hence we have |[] ∩ | = |[] ∩ 0− 0 · 0| + |[] ∩ 1− 1 · 1| ⩽ |− 1 [0] ∩ 0| + |− 0 [1] ∩ 1|. (1)
If both ( − 1) and ( − 0) are positive, then the right hand side of (1) is bounded above by ( − 1) + ( − 0), since is a multipacking in for each ∈ {0, 1}. Since (0 + 1) = ( − 0) ⩾ ( − 1) ⩾ , this bound is at most and we are done. If ( − 1) < 0, then the right hand side of (1) is bounded above by 0 + ( − 0) ⩽ . The case when ( − 0) < 0 is similar. If ( − 1) = 0 but 0 > 0, then the right hand side of (1) is bounded above by 1 + ( − 0) ⩽ . The case when ( − 0) = 0 but 1 > 0 is also similar.
We are only left with two boundary cases, viz., − 1 = 0 = 0 and − 0 = 0 = 1. Here we use the fact that − 0 = max(|0|, 2) + max(|1|, 2) − 1 ⩾ max{|0|, |1|} + 1. In the first boundary case, since 0 = 0, we have 1 = ( − 0) ⩾ |1| + 1. Further since − 1 = 0 in this case, we have = 1 ⩾ |1| + 1. Hence, the right-hand side of (1), which is at most 1 + |1|, is bounded above by . The second boundary case ( − 0 = 0 = 1) is similar.
It should be noted that if = 0 + |0| + |1| − 1 (rather than 0 + max(|0|, 2) + max(|1|, 2) − 1), then for small values of 0 (particularly 0 = 1 or 2), the resulting set does not form a valid multipacking.
Corollary 2.4. Let 0 ⩾ 1 be two positive integers. Let mp(0 ) ⩾ 0 and mp(1 ) ⩾ 1. Then mp() ⩾ 0 + 1, where
= 0 + max(0, 2) + max(1, 2) − 1.
This recursive approach leads to a general lower bound of the multipacking number on hypercubes, which we formalize in the subsequent results.
Lemma 2.5. For any positive integer , mp(2) ⩾ .
Proof. We use induction on . The statement is easy to verify for ⩽ 2 and holds for = 3 by Proposition 2.1. Suppose ⩾ 4 and that the statement holds for all natural numbers less than . Due to the induction hypothesis, we have
︁( mp 2⌈ 2 ⌉ ︁) ⩾ ︂⌈ ⌉︂ 2
︁( , and mp 2⌊ 2 ⌋ ︁) ⩾ ︂⌊ ⌋︂ 2 .
Since ⌊︀ ⌋︀ ⩾ 2, by Corollary 2.4, we have
2 where mp() ⩾ ︂⌈ ⌉︂ 2 + ︂⌊ ⌋︂ 2
= ,
Proof of the lower bound of Theorem 1.4. If = 1, then mp(1) > 0. When is an even positive integer, the proof follows from Lemma 2.5. When = 2 + 1 is odd for some positive integer , by Lemma 2.5 and Observation 2.2 we have, mp() = mp(2+1) ⩾ mp(2) ⩾ = ⌊︁ ⌋︁
. 2 arbitrarily large.
Though we cannot improve the lower bound of ⌊︀ ⌋︀ in general, we show that mp() − 2
2 ︀⌊ ⌋︀ can be Proposition 2.6. For every positive integer , mp( ) ⩾ 2 + log2 − 1 , where = 2+1 2 − . for ⩾ 2, we have mp( ) ⩾ , due to Corollary 2.4., where Proof. We construct a specific sequence of hypercubes { } by repeatedly applying Corollary 2.4 starting from 3, for which the multipacking number is 2. Hence, we consider 1 = 3 and 1 = 2. At each step, we consider two identical copies multipacking of the hypercube − 1 , and using Lemma 2.3, we obtain a multipacking of . Therefore, using mp(− 1 ) ⩾ − 1 as an inductive hypothesis On solving these recurrence relations with initial conditions 1 = 3 and 1 = 2, we obtain From = 2+1 mp( ) ⩾ , we have − , we get = 2 + 2 , and using ⩽ 2+1, it follows that ⩾ log2 − 1. As = − 1 + 2− 1 − 1, = 2− 1. = 2+1
− , = 2 for all ⩾ 1. mp( ) ⩾ +
Let’s recall a classic result due to Spencer [
Theorem 2.7. [
The next lemma establishes an upper bound on mp() using this bound.
Suppose we have a finite family of sets with finite elements, and we intend to color the underlying set with two colors such that each subset has roughly half of each color. The discrepancy quantifies how unbalanced any set in the family can be under the best possible two-coloring of the underlying set. Formally, let be a family of subsets of Ω , and consider the coloring as a mapping Suppose for every ⊆ Ω , () = ∑︀∈ (). Then, the discrepancy of with respect to is defined as The discrepancy of is defined as : Ω
→ {− 1, +1}. disc(, ) = max | ()|.
∈ disc() =
min :Ω→{− 1,+1}
disc(, ).
disc() ⩽ 6√. mp() ⩽ 2
+ 6√︀2 mp() Proof. Let = {1, 2, . . . , } be a maximum multipacking in of size (⩾ 2 ). For each ∈ , we construct a set ⊆ [] comprising of the coordinates at which has 1, and = [] ∖ . In particular, contains the coordinate values at which has 0. Now, consider the family of 2 sets = {1, 1, 2, 2, . . . , , }, with the underlying set Ω = [2 ] ⊇ []. Let be a mapping such that disc(, ) = disc(). For each ∈ [], if () = − 1, then we flip the bit at the -th coordinate for all the vertices of . All such lfippings induce an automorphism on the vertex set of . Hence, the set contains new vertices of . Further, a bit-flipping preserves the hamming distance, and therefore is still a multipacking in .
Since, for each ∈ [], | ()|, | ()| ⩽ disc(), the number of ones in () is at most ︁( |2| + disc2() )︁ + ︁( |2| + disc2() )︁ = 2 + disc(). Hence wt() ⩽ 2 + disc() for every ∈ after flipping. This means that, after flipping, ⊆ 2 +disc()[0]. As is still a multipacking, we have
| | ⩽ 2 + disc() ⩽ 2 + 6√︀2, where the last inequality is due to Theorem 2.7. As is a maximum multipacking in , we have the desired upper bound.
Proof of the upper bound of Theorem 1.4. The upper bound mp() ⩽ 2 + 6√2 in Theorem 1.4 now follows from Lemma 2.8 since mp() ⩽ .
The author(s) have not employed any Generative AI tools.