On the multipacking number of grid graphs
Laurent Beaudou Richard C. Brewster

2120193234452
The Unmanned Aerial Vehicle Benchmark:
 Object Detection and Tracking
    ^1Dawei Du, ^2Yuankai Qi, ^2Hongyang Yu, ^1Yifan Yang, ^1Kaiwen Duan, ^1Guorong Li, ^3Weigang Zhang, ^1Qingming Huang, ^4Qi Tian
    December 30, 2023
====================================================================================================================================





  In 2001, Erwin introduced broadcast domination in graphs. It
  is a variant of classical domination where selected vertices may
  have different domination powers. The minimum cost of a dominating
  broadcast in a graph G is denoted (G). The dual of this
  problem is called multipacking: a multipacking
  is a set M ⊆ V(G) such that for any vertex v and
  any positive integer r, the ball of radius r around v contains
  at most r vertices of M. The maximum size of a
  multipacking in a graph G is denoted (G). Naturally (G)
  ≤(G). Earlier results by Farber and by Lubiw show that
  broadcast and multipacking numbers are equal for strongly chordal
  graphs.
  
  In this paper, we show that all large grids (height at least 4 and
  width at least 7), which are far from being chordal, have their
  broadcast and multipacking numbers equal.
  





§ INTRODUCTION


Given a graph G with vertex set V and edge set E, a dominating broadcast of G is a function f from V to
ℕ such that for any vertex u in V, there is a vertex
v in V with f(v) positive and greater than the distance from u
to v. Define the ball of radius r around v by N_r(v) =
{ u : d(u,v) ≤ r }.  Thus a dominating broadcast is a cover of
the graph with balls of several positive radii. The cost of a
dominating broadcast f is ∑_v ∈ V f(v) and the minimum cost
of a dominating broadcast in G, its broadcast number, is
denoted (G).


  One may consider the cost to be any function of the powers
  (for example the sum of the squares), see e.g. <cit.>. We shall stick to the
  classical convention of linear cost.


The dual problem of broadcast domination is multipacking. A
multipacking in a graph G is a subset M of its vertices such that
for any positive integer r and any vertex v in V, the ball of
radius r centred at v contains at most r vertices of M.  The
maximum size of a multipacking of G, its multipacking number, is denoted (G). 
We may write 
and  when the graph in question is clear from context or
unimportant.

Broadcast domination was introduced by Erwin <cit.> in his doctoral thesis in 2001. Multipacking was then
defined in Teshima's Master's Thesis <cit.> in 2012, see
also <cit.>. However, this work fits into the general
study of coverings and packings, which has a rich history in Graph
Theory, see for example the monograph by Cornuéjols <cit.>. 

Since minimum dominating broadcast and multipacking are dual problems,
we know that for any graph G,

    (G) ≤(G).

A natural question comes to mind. Under which conditions are they
equal? For example, it is known that strongly chordal graphs have
their broadcast and multipacking numbers equal. This follows from a
primal-dual algorithm of Farber <cit.> applied to
Γ-free matrices, used to solve the (weighted) dominating set
problem for strongly chordal graphs. The work of
Lubiw <cit.> shows the vertex-neighbourhood ball
incidence matrix is Γ-free for strongly chordal graphs, and
hence the primal-dual algorithm can also be used to solve the
broadcast domination problem for strongly chordal graphs.  For trees,
direct proofs of (T) = (T) and linear-time algorithms to find
(T) appear in <cit.> (see
also <cit.>). For strongly chordal graphs,
Farber's algorithm runs in O(n^3) time. The general broadcast
domination problem can be solved in O(n^6)
time <cit.>.  In this paper we study grid
graphs which are far from being strongly chordal (or even chordal). We
show the following theorem.

  
  For any pair of integers n ≥ 4 and m ≥ 4,
  
    (P_n  P_m) = (P_n  P_m).

  with the exception of P_4  P_6 where (P_4  P_6) = 4
  and (P_4  P_6) = 5.

This gives an infinite family of non-chordal graphs for which =. Another such family is the cycles of length 0 modulo 3.  It
is trivial to verify that (C_3k) = (C_3k) = k.

Dunbar et al. <cit.> gave the exact value of the broadcast
number for grids.


  For any pair of positive integers n and m, 
  
    (P_n  P_m) = ⌊n/2⌋ + ⌊m/2⌋.

  


 
The value of (P_n  P_m) given by Theorem <ref> is
the radius of the grid. Since there is always a dominating broadcast
with cost (G) <cit.>, and our proof of
Theorem <ref> yields a multipacking of size (G), this
paper gives an alternative proof of Theorem <ref>.




§ PRELIMINARIES AND SMALL GRIDS


We use standard notation throughout the paper.  Specific to our work
is the following: the grid P_n  P_m has n rows and m
columns.  We may also say the grid has height n and length m.  The
vertex in row i and column j is denoted v_i,j.  As a
convention, the vertex v_0,0 is the bottom, left corner of the
grid.  The integers between k and ℓ inclusive are denoted
k,ℓ.

The proof of Theorem <ref> is technical. In order to
ease the process, we start with an easy counting lemma.


  
  Let G be a graph, k be a positive integer and
  u_0,…,u_3k be an isometric path in G. 
  Let  be the
  set of every third vertex on this path. Then, for any positive integer r and any ball
  B of radius r in G,
  
    |B ∩ P| ≤⌈2r+1/3⌉.




  Let B be a ball of radius r in G, then any two vertices in B
  are at distance at most 2r. Since the path (u_0,…,u_3k)
  is isometric the intersection of the path and B is included in a
  subpath of length 2r. This subpath contains at most 2r+1
  vertices and only one third of those vertices can be in P.


For the sake of completeness, we also determine the multipacking
numbers of grids with height 2 and 3.


Let n be a positive integer.  Then

    (P_n  P_2) = 
    ⌈2n/5⌉








Let P be a maximum multipacking of P_n  P_2. 
We claim that no five consecutive columns contain three members of P.
Suppose to the contrary that columns i to i+4 contain three members of P.
No two consecutive columns each contain a member of P, as 
any pair of vertices in P_2  P_2 are at distance at most 2 apart
(and thus in a ball of radius 1).
Hence, the three elements are without loss of generality
{ v_i,0, v_i+2,1, v_i+4,0}.  
However, this implies |N_2[v_i+2,0] ∩ P| = 3, a contradiction.
  
Writing n=5q+r, 0 ≤ r ≤ 4, we conclude that
the first 5q columns of the grid contain at most 2q elements of P.
Next, it is easy to verify that (P_1  P_2) = (P_2  P_2) = 1,
and (P_3  P_2) = (P_4  P_2) =2.  
Let s be the number of elements of P in the final r columns
of the grid.  Then, s = 0 if r=0,
s ≤ 1 if r = 1, 2 and s ≤ 2 if r=3,4. 
Thus, |P| ≤ 2q + ⌈ 2r / 5 ⌉.
Equivalently, |P| ≤⌈2n/5⌉.  

On the other hand, consider the set P defined as follows.

    v_i,0∈ P        i ≡ 0 5
    
    v_i,1∈ P        i ≡ 2 5

Consider a ball B of radius r ≥ 2.  It contains 
vertices from at most 2r+1 consecutive columns of P_n  P_2.  
By construction, every five consecutive columns contain at most 2 
elements of P.  

    |B ∩ P| ≤ 2 ⌈(2r+1)/5⌉

It is straightforward to check that, 
2 ⌈ (2r+1)/ 5 ⌉≤ r for r ≠ 1, 3, 5. 
(For r<10, simply evaluate  2 ⌈ (2r+1)/ 5 ⌉.
For r ≥ 10, 2 ⌈ (2r+1)/ 5 ⌉≤ 2 (2r/5 + 1) ≤ r.)
It is easy to check that each ball of radius 1 contains at most one
element of P. When r=3, B contains vertices from 7 columns of 
which at most 3 columns may contain packing vertices.  Similarly, 
when r=5, we observe that any 11 consecutive columns contain at 
most 5 packing vertices.


We now turn to the special case when m=3. The following result gives
(P_n  P_3).  Since (P_n  P_3) = ⌊n/2⌋ + 1, we note that = for n ≢0 4.


Let n be a positive integer.  Then

    (P_n  P_3) = {[         ⌊n/2⌋       n ≡ 0 4;     ⌊n/2⌋ + 1 n ≡
      1,2,3 4 ] .




Since rad(P_n  P_3) = ⌊ n/2 ⌋ + ⌊ 3/2
⌋, we know that (P_n  P_3) ≤⌊ n/2 ⌋ + 1.
Given a multipacking P of P_n  P_3 and any four consecutive
columns say i, i+1, i+2, i+3, if P has three members in
these columns, then without loss of generality they belong to columns i,
i+2, i+3.  Moreover, we can assume that the two in columns i+2, i+3 are
v_i+2,2 and v_i+3,0.  The only vertices that are not within
distance 2 of either of these two packing vertices are v_i,0 and v_i,1. 
However, all three of these vertices are in a ball of radius 2 centred at
v_i+2,0 in the former case and v_i+2,1 in the latter, a contradiction. 
Thus, the four columns contain at most 2 packing vertices. 
Specifically, in the case n = 4q, (P_n  P_3) ≤ 2q = ⌊ n/2 ⌋.

On the other hand, consider the set P defined as follows.

    v_i,0∈ P        i ≡ 0 4
    
    v_i,2∈ P        i ≡ 1 4

As the minimum distance between vertices in P is 3, no ball of
radius 1 contains more than one element of P.  Consider a ball B
of radius r ≥ 2.  The ball contains vertices from at most 2r+1
consecutive columns.  We need to confirm that the ball has at most r elements of P.
First, suppose that r = 2t.  By symmetry, we may assume that the left most column
of B is in { 0, 1, 2, 3 }.  If the left most column is 2 or 3,
then B contains vertices from columns { 4, 5, …, 4t + 2, 4t + 3 }.
Each contiguous block of four columns contains two members of P, giving B 
has a total of at most 2t = r vertices of P.  
If the left most column of B is 0 or 1,
then B covers columns 0, 1, …, 4t or 1, …, 4t, 4t+1.
In both cases, B has exactly 2t+1 columns with a vertex of P.
However, in both cases v_1,2 and v_4t,0 are at distance 4t+1 = 2r+1
apart and thus, at most one belongs to B.  In all cases, |B ∩ P| ≤ r.
If r = 2t+1, the analysis is similar.  
Either the 4t+3 columns of B
contain at most 2t+1 = r vertices of P, or 
the ball B has 2t+2 = r+1 columns containing vertices of P, but there is a pair
(for example { v_0,0, v_4t+1,2}) at distance 2r+1, in which case
B itself contains at most r vertices of P.






§ MULTIPACKING NUMBER FOR LARGE GRIDS



In this section, we prove Theorem <ref>. The radius of a
grid graph P_n  P_m is ⌊n/2⌋ + ⌊m/2⌋. Since the broadcast number of a graph is at most
its radius, it is sufficient to find a multipacking of size ⌊n/2⌋ + ⌊m/2⌋. We now proceed with
the construction of such multipackings.




 §.§ Restriction to even sizes


First, we shall prove that we can restrict ourselves to cases when n
and m are both even numbers. Because of the singularity for the grid
of size 4 × 6, we need to check the grids of sizes 5 × 6
and 4 × 7 by hand (see Figure <ref>). Now, suppose that
n is odd. Then, n-1 is even and is at least 4. Moreover the n-1
× m grid is not 4 × 6 since we ruled out the 5 × 6
and 4 × 7 cases. Thus, if we know that the grid of size n-1
× m has a multipacking of size n-1/2 + ⌊m/2⌋, which is equal to ⌊n/2⌋ +
⌊m/2⌋, we can add an empty column in the middle
of this grid. We obtain a multipacking of the desired size for our
grid. Indeed, given a vertex v from the smaller grid, the ball of
radius r with centre v in the larger grid only contains vertices
of the packing which were at distance at most r from v in the
smaller grid. A ball of radius r centred at a vertex of the new
column only contains vertices of the packing which are within distance
r of both its neighbours from the former grid. Thus, these balls
cannot contain more than r elements of the packing which satisfies
our claim. The same reasoning works for m.

  

  The remainder of the proof is concerned with grids with even
  dimensions. Small cases require some specific care so that we will
  treat them after the general case. In all cases, we shall use a
  systematic way of selecting vertices along the sides of the grid. We
  describe them in the following paragraph.

  

 §.§ The i-pattern

  
  Fix an integer i. Given a path v_0 v_1 … v_z-1 of order
  z greater than or equal to 3i, the i-pattern on this
  path consists in selecting every third vertex from v_0 to
  v_3(i-1) and then every fourth vertex starting from v_3i (if
  it exists). Note that the i-pattern on a path of order z selects
  exactly i vertices from the beginning and one fourth (rounded
  up) of the rest. This amounts to i + ⌈z-3i/4⌉ which can be simplified.
  
    The i-pattern on a path of order z  selects exactly ⌈z+i/4⌉ vertices.

  Moreover, the density of the i-pattern is bounded above by a
  function of i. By this, we mean that a subpath of length ℓ of
  v_0 v_1 … v_z-1 cannot hit too many vertices of the
  i-pattern. If ℓ is at least 3i, it could take the whole
  beginning (i vertices) and a fourth of the rest. This amounts to
  i + ⌈ℓ + 1 - 3i/4⌉ which equals ⌈ℓ+1+i/4⌉. Whenever ℓ is strictly less than
  3i, it would take at most ⌈ℓ+1/3⌉
  vertices. But in that case, 
  
           ⌈ℓ+1/3⌉    ≤⌈4ℓ+4/12⌉      

               ≤⌈3ℓ+3+ℓ+1/12⌉      

               ≤⌈3ℓ+3+3i/12⌉   (since  ℓ+ 1 ≤3i )   

               ≤⌈ℓ+1+i/4⌉.      
  
  In the end, we may state that
  
    a subpath of length ℓ hits at most ⌈ℓ+1+i/4⌉ vertices on a i-pattern.


  

 §.§ Large grids

  
  As said before, small grids require some extra-care. In this part,
  we only consider grids with dimensions at least 8 in both directions. Fix
  n and m two even integers greater than or equal to 8. We let
  k=n/2 and k'=m/2. We view each side of the grid
  as a path from which we remove the last three vertices (see
  Figure <ref>). In these paths, we pack an adequate
  number of vertices using a specific i-pattern. Finally,
  we will estimate an upper bound on the number of such vertices in a
  ball of size r. This will cover most of the radii but the
  last few ones will be treated using some tailor-made arguments.
  
  
  We use the i-patterns (where i = 0, 1, or 2) to select vertices on 
  “horizontal” and  “vertical” sides.   
  The packing on the horizontal sides is as follows (with the vertical sides
  being similar).  Our choice of i depends on the parity of k.  
  In all cases, 2k-4 ≥ 3i.
  If k is even, then we use a 1-pattern on the top 
  (0,m-1), (3,m-1), (7,m-1), …, (n-5,m-1) and a 1-pattern
  on the bottom (n-1,0), (n-4,0), (n-8,0), …, (4,0).  
  In this case we shall write i_t = i_b = 1.  If k is odd,
  we use a 2-pattern on the top (0,m-1), (3,m-1), (6,m-1), (10,m-1), …, (n-4,m-1)
  and a 0-pattern on the bottom (n-1,0), (n-5,0), …, (5,0).
  In this case we write i_t = 2 and i_b = 0.
  Using (<ref>), we see there are exactly k/2
  vertices selected on a (horizontal) side, when k is even.
  When k is odd ⌊k/2⌋ are selected on the bottom while 
  ⌈k/2⌉ are selected on the top.  In all cases n/2=k
  vertices are selected. These selections are depicted on Figure <ref>
  for n=16 and n=18 (only the top and bottom sides of the grid are
  drawn). We call H the set of vertices selected on the horizontal
  paths. Similarly we select a total of k' vertices on the vertical 
  sides and let V denote these vertices. 
  After this process, we have a set P of k+k'
  vertices. We shall prove that it is a valid multipacking.
  
  
  

  
Most balls are valid.
  Let r be some integer between 1 and k+k'-5, and let B be a ball
  of radius r. 
  
  
  * If B does not intersect any side of the grid, then
    its intersection with P is empty and |B ∩ P| ≤ r
    trivially. 
    
  
  * Suppose now that B intersects only one side of the
    grid, or two consecutive sides. Then its intersection with P lies
    on an isometric path of the grid where selected vertices are at
    distance at least 3 from each other. Thus the cardinality of B ∩
    P is bounded above by ⌈2r+1/3⌉ which
    is at most r since r is a positive integer (see
    Lemma <ref>).
    
  
  * Now if B intersects two opposite sides of the grid (let them
    be top and bottom), let y denote the ordinate of the center of
    B. Recall that bottom has ordinate 0 while top has ordinate
    m-1. Now observe that the metric induced by the grid is similar
    to ℓ_1 metric. Thus B intersects the bottom side on a
    subpath of length at most 2(r-y) and the top side on a subpath
    of length at most 2(r-2k'+1+y). We claim that in most cases |B
    ∩ H| ≤ r-k'+2. Only in very specific cases can |B ∩ H|
    be equal to r-k'+3. 

    Let x_b be the difference between 2(r-y) and the actual length
    of the intersection between B and the bottom part of H (recall
    that the bottom part of H does not include the last three
    vertices as depicted on Figures <ref>
    and <ref>). Similarly, we define x_t for the top
    part of H. Then B intersect the bottom part of H on a
    subpath of length 2(r-y) - x_b. We now use
    (<ref>):
    
    |B ∩ H|    ≤⌈2(r-y) - x_b + 1 + i_b/4⌉ + ⌈2(r-2k'+1+y) -x_t + 1 + i_t/4⌉
       ≤⌈2(r-y) + 1 + i_b - x_b/4⌉ + ⌈2(r+y)+3+i_t - x_t/4⌉ - k'.

    Notice that r-y and r+y have same parity. First suppose they
    are both odd. Then 2(r-y) - 2 and 2(r+y) - 2 are multiples of
    4. We can rewrite our bound.
    
    |B ∩ H|    ≤⌈2(r-y) - 2 + 3 + i_b - x_b/4⌉ + ⌈2(r+y)-2+5+i_t - x_t/4⌉ - k' 
       ≤⌈3 + i_b - x_b/4⌉ + ⌈5+i_t - x_t/4⌉ +r - 1 - k'.

    Our pattern choice is either i_b = i_t = 1 or i_b = 0 and i_t
    = 2. In both cases, the ceilings add up to at most 3. So |B ∩
    H| ≤ r - k' + 2 when r-y is odd. Now suppose that r-y is
    even. Then the rewriting is straightforward.
    
    |B ∩ H|    ≤⌈2(r-y) + 1 + i_b - x_b/4⌉ + ⌈2(r+y)+3+i_t - x_t/4⌉ - k' 
       ≤⌈1 + i_b - x_b/4⌉ + ⌈3+i_t - x_t/4⌉ +r - k'.

    When the pattern is i_b = i_t = 1, ceilings add up to at most 2
    and once again |B ∩ H| ≤ r - k' + 2. When i_b = 0 and
    i_t = 2, ceilings can unfortunately sum up to 3. But for this,
    both x_b and x_t must be 0. Let us be more precise. It means
    that both bottom and top intersections must be full (subpaths of
    length 2(r-y) and 2(r-2k'+1+y)). Moreover, B ∩ H must use the
    corner vertex in the top part since otherwise, it would be
    intersecting a path which is nothing but a 1-pattern (or a
    0-pattern). As a consequence, the center of B must be at
    distance exactly r from the top left corner. Moreover, B
    cannot reach the top right corner of the grid (otherwise, x_t
    would be strictly positive). Similarly, B cannot reach the
    bottom left corner since it is out of the bottom part of H and
    it would require x_b to be strictly positive. 

    
    
  * If B intersects only the top and bottom part of H, then
      |B∩ H| ≤ r-k'+3 ≤ r since k' is at least 4.

    
  * If B intersects also exactly one vertical side. This one
      can contribute at most for ⌈k'/2⌉ (by our
      choice of P). Thus, in most cases
      
    |B ∩ P|    ≤ r - k' + 2 + ⌈k'/2⌉
       ≤ r - k' + 2 + k'/2 + 1/2
       ≤ r - 1/2 (k'-5)

      which is at most r since k' is not less than 4 (when k' =
      4 we observe |B ∩ P| ≤ r + 1/2 implies |B ∩
      P| ≤ r since |B ∩ P| is an integer).  In the special
      case when |B ∩ H| is r - k' + 3, recall that the vertical
      side cannot use the corner so it contributes at most for ⌈k'/2⌉-1 and the same conclusion holds.
 
      
     
  * Finally, if B intersects all four sides, we may use the
       corner observation to state that at most one of the directions
       (vertical or horizontal) can contribute for r-k'+3 (or
       r-k+3). The other direction contributes at most for r-k+2
       (or r-k'+2) so that
      
    |B ∩ P|    = |B ∩ H| + |B ∩ V|
       ≤ 2r - (k+k') + 5.

      This quantity is less than or equal to r whenever r is
      k+k'-5 or less.
      
    
    
 
















































  

















  
  











  







  
  

  

  
Balls with a big radius.
  To finish our proof, we only need to verify that balls with a radius
  r between k+k'-4 and k+k'-1 verify our constraint.

  Let us treat the maximum radius k+k'-1. Note that since n and
  m are both even, this grid, if seen as a chequerboard, has two 
  diagonally opposite white corners and two diagonally opposite black
  corners.  Suppose a ball of radius k+k'-1
  contains all the vertices of P. Then it must contain the four
  corners of the grid. Since opposite corners are at distance 2k +
  2k' -2 it means that the centre of the ball is the middle vertex of
  a shortest path between opposite corners. But this middle vertex
  must be white for one pair of corners and must be black for the 
  other pair, which is impossible. Thus every ball of radius k+k'-1
  misses at least one corner.

  Now consider a ball of radius k+k'-2. Since both pairs of opposite
  corners are at distance 2k + 2k' -2, at most one corner of each
  pair can be in a ball of such radius. Thus, such a ball misses at
  least two corners.

  Concerning radius, k+k'-4, we can match each corner vertex with
  the second selected vertex from the opposite side. The distance
  between them is 2k+2k'-5 (corner to a 2-pattern or to a 1-pattern)
  or 2k+2k'-6 (corner to a 0-pattern) depending on the chosen
  pattern. In any case, since vertices in the ball cannot have
  distance more 2k+2k'-8, such a ball misses at least 4 vertices
  from the total and is valid.

  Finally, we are left with balls of radius k+k'-3. We may again
  consider the same matching. If k or k' is even, we have at least
  one direction with two 1-patterns and so at least three of the pairs
  are at distance 2k+2k'-5. So the ball misses at least three
  vertices and is valid. The last case is when both k and k' are
  odd. In that case, our matching has two pairs at distance 2k+2k'-5
  (from which the ball misses at least two vertices) and two pairs
  at distance 2k+2k'-6. As for radius k+k'-1, both last pairs are
  on two different colors of the chequerboard (black and white) so
  that at least one of the four concerned vertices is missed. In the
  end, the ball misses at least three vertices and is valid.

  This concludes the proof for grids with sizes at least 8 in both
  directions.

  

 §.§ Long grids

  

  The previous discussion leaves out all grids with one of their
  dimensions either 4 or 6. In this section, we provide a way of
  tackling long grids (for which k ≥ 3k'- ℓ where ℓ
  depends on the parity of k+k'). In the end,
  there will only remain four cases to study.

  
  We shall pack vertices only on the top and bottom sides of the grid. We
  consider the whole sides (not the 2k-3 first vertices as in
  Subsection <ref>). 
  Recall to pack an i-pattern on a horizontal side requires 3i ≤ n-1.   


  If k and k' have same
  parity, we use a (2k'-3)-pattern on both top and bottom sides. 
  This requires 3(2k'-3) ≤ n-1 or 3k'-4 ≤ k.
  If k and k' have different parities, 
  we use a (2k'-5)-pattern on one side (say bottom) and
  a (2k'-1)-pattern on the other. This requires 3k'-1 ≤ k.  



  By (<ref>), this process selects
  
    ⌈2k+2k'-3/4⌉ + ⌈2k+2k'-3/4⌉ or ⌈2k+2k'-1/4⌉ + ⌈2k+2k'-5/4⌉

  vertices. In both cases, this can be simplified as k+k' (in the
  first case, k+k' is even, while it is odd in the latter).
  
  Now, if a ball B of radius r intersects only one horizontal side
  of the grid, this intersection lies on an isometric path from which
  we selected at most every third vertex. Then by
  Lemma <ref>, it cannot contain strictly more than r
  vertices. Suppose that the ball B intersects both paths. Like in
  the previous subsection, if this ball has its centre on a vertex with
  ordinate y (0 being the bottom and m-1 being the top), then it
  intersects the bottom on a path of length at most 2(r-y) and the
  top on a path of length at most 2(r-2k'+1+y). Then we
  use (<ref>). If both sides are packed with
  (2k'-3)-patterns,
  
    |B ∩ H|    ≤⌈2(r-y) + 2k'-2/4⌉ + ⌈2(r-2k'+1+y) + 2k'-2/4⌉
       ≤⌈2(r-y+k')-2/4⌉ + ⌈2(r-k'+y)/4⌉.

  And since r-y+k' and r+y-k' have same parity, one of the
  ceilings adds 1/2, and
  
    |B ∩ H|    ≤2(r-y+k')-2/4 + 2(r-k'+y)/4 + 1/2
       ≤ r.

  Similarly, if we use the (2k'-5)-pattern on bottom and the
  (2k'-1)-pattern on the top, we have 
  
    |B ∩ H|    ≤⌈2(r-y) + 2k'-4/4⌉ + ⌈2(r-2k'+1+y) + 2k'/4⌉
       ≤⌈2(r-y+k')-4/4⌉ + ⌈2(r-k'+y)+2/4⌉.

  Once again, the rounding adds at most 1/2 and 
  
    |B ∩ H|  ≤ r.


  When k' = 2 and k is even, we use a 2k'-3 = 1 pattern.
  Thus the previous paragraph is valid for all even k ≥ 2.
  When k is odd we use a 0-pattern and a 3-pattern. This requires
  k ≥ 5.  In particular, we have valid multipackings for 4 × n
  for any even n ≥ 4 and n ≠ 6.  
  In the same manner the previous paragraph gives a valid 
  multipacking of order k+k' when k' = 3 provided 
  k ≥ 8 for even k and k ≥ 5 for odd k. 
  Consequently we have packings of grids with dimensions 6 × n 
  for even n ≠ 6, 8, 12.  This concludes the proof for long grids.  
  (We remark the above arguments
  show for a fixed k' and sufficiently large k, there is an 
  optimal multipacking selecting vertices only on the horizontal sides.)
  
  

 §.§ Remaining cases

  
  Subsection <ref> covers large grids (4 ≤ k ≤ k'),
  and Subsection <ref> covers long grids (2 ≤ k' ≤
  (k+ℓ)/3). There are four remaining cases that can be checked by
  hand, and have been verified using SageMath.






  Three are depicted on Figure <ref>.
  
  

  Finally, the 6 × 4 grid is the
  only grid with dimensions at least 4 and multipacking number strictly
  smaller than expected. It is 4 while its broadcast domination number
  is 5. This completes the proof of Theorem <ref>.




§ ACKNOWLEDGEMENT


This research was initiated when the first author and Florent Foucaud
visited the second author at Thompson Rivers University (Kamloops, BC,
Canada) in June 2016. First author is grateful to Université Clermont
Auvergne which was his institution at that time.

Both authors are grateful to anonymous referees who pointed out a flaw
in the proof of the main theorem in the first submitted version of
this article.



00
Brewster2013 R. C. Brewster, C.M. Mynhardt and L. Teshima,
  New bounds for the broadcast domination number of a graph,
  Central European Journal of Mathematics, 11 (2013),
  1334–1343.

Brewster2017 R. C. Brewster, G. MacGillivray and F. Yang, 
Broadcast domination and multipacking in strongly chordal graphs,  
Discrete Applied Mathematics, accepted.

Cornuejols2001 G. Cornuéjols. Combinatorial
  Optimization: packing and covering. CBMS-NSF regional conference
  series in applied mathematics, vol. 74. Society for Industrial and
  Applied Mathematics (SIAM), Philadelphia, 2001.

Dabney2007 J. Dabney 
A linear-time algorithm for broadcast domination in a tree, 
Master's Thesis, Clemson University, 2007.

Dabney2009
J. Dabney, B.C. Dean, S.T. Hedetniemi, 
A linear-time algorithm for broadcast domination in a tree. 
Networks, 53 (2009), 160–169.
    
dun_al_2006 J. E. Dunbar, D. J. Erwin, T. W. Haynes,
S. M. Hedetniemi and S. T. Hedetniemi, 
Broadcasts in graphs, 
Discrete Applied Mathematics, 154 (2006), 59–75.

Erwin2001 D. J. Erwin, 
Cost domination in graphs, PhD Thesis, Department of Mathematics, Western Michigan University, 2001.

Erwin2004 D. J. Erwin, 
Dominating broadcasts in graphs, 
Bulletin of the ICA, 42 (2004), 89–105.

Farber84 M. Farber, 
Domination, Independent Domination, and Duality in Strongly Chordal Graphs, 
Discrete Applied Mathematics, 7 (1984), 115–130.
   
HeggernesLokshtanov2006 P. Heggernes and D. Lokshtanov, Optimal broadcast domination in polynomial time, Discrete Mathematics,  306 (2006), 3267–3280.

Lubiw82 A. Lubiw, 
Γ-free Matrices, 
Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1982.

Lubiw87 A. Lubiw, 
Doubly Lexical Orderings of Matrices, 
SIAM Journal on Computing, 16 (1987), 854–879.

Teshima2012 L. Teshima, 
Broadcasts and multipackings in graphs, 
Master's Thesis, Department of Mathematics and Statistics, University of Victoria, 2012.














