Prosenjit Bose

Valentin Gledel
email: valentin.gledel@liris.cnrs.fr

Claire Pennarun
email: claire.pennarun@lirmm.fr

Sander Verdonschot
email: sander@cg.scs.carleton.ca

Power domination on triangular grids with triangular and hexagonal shape *

The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph G and a set S ⊆ V (G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct neighbors, and then each time a vertex in M has exactly one neighbor not in M , this neighbor is added to M . The power domination number of a graph G is the minimum size of a set S such that this process ends up with the set M containing every vertex of G. We show that the power domination number of a triangular grid H k with hexagonal-shaped border of length k -1 is k 3 , and the one of a triangular grid T k with triangular-shaped border of length k -1 is k 4 .

Introduction

Power domination is a problem that arose from the context of monitoring electrical systems [START_REF] Mili | Phasor measurement placement for voltage stability analysis of power systems[END_REF][START_REF] Baldwin | Power system observability with minimal phasor measurement placement[END_REF], and was reformulated in graph terms by Haynes et al. [START_REF] Haynes | Domination in graphs applied to electric power networks[END_REF].

Given a graph G and a set S ⊆ V (G), we build a set M as follows: at first, M is the closed neighborhood of S, i.e., M = N [S], and then iteratively a vertex u is added to M if u is the only neighbor of a monitored vertex v that is not in M (we say that v propagates to u). At the end of the process, we call M the set of vertices monitored by S. We say that G is monitored when all its vertices are monitored. The set S is a power dominating set of G if M = V (G), and the minimum cardinality of such a set is the power domination number of G, denoted by γ P (G).

Power domination has been particularly well studied on regular grids and their generalizations: the exact power domination number has been determined for the square grid [START_REF] Dorfling | A note on power domination in grid graphs[END_REF] and other products of paths [START_REF] Dorbec | Power domination in product graphs[END_REF], for the hexagonal grid [START_REF] Ferrero | Power domination in honeycomb networks[END_REF], as well as for cylinders and tori [START_REF] Barrera | Power domination in cylinders, tori, and generalized Petersen graphs[END_REF]. These results are particularly interesting in comparison with the ones on the same classes for (classical) domination: for example, the problem of finding the domination number of grid graphs P n × P m was a difficult problem which was solved only recently [START_REF] Gonçalves | The domination number of grids[END_REF]. They also rely heavily on propagation: it is generally sufficient to monitor (with adjacency alone) a small portion of the graph in order to propagate to the whole graph.

We continue the study of power domination in grid-like graphs by focusing on triangular grids with both hexagonal-shaped border and triangular-shaped border. We prove the following results: Theorem 1. Let H k be a triangular grid with a regular hexagonal-shaped border of length k -1. For every positive integer k, γ P (H k ) = k 3 .

Theorem 2. Let T k be a triangular grid with an triangular-shaped border of length k -1. For every positive integer k, γ

P (T k ) = k 4 .
If S is a power dominating set, there always exists some total order m 1 , . . . , m |V (G)\N [S]| on the vertices of V (G)\N [S], such that m i can be monitored next if M = {m 1 , . . . , m i-1 }. We arbitrarily fix one such total order and define the set M [t] as follows: M [0] = N [S], and M [t + 1] = M [t] ∪ {m t+1 }. The study of some invariants of these sets is one of the keys to our proofs for the upper bounds on the power domination number for both the families H k and T k .

Hexagonal-shaped border

A triangular grid with hexagonal-shaped border H k has vertex set V (H k ) = {(x, y, z) | x, y, z ∈ [0..2k -2], x -y + z = k -1}. Two vertices v and v are adjacent if and only if

|v x -v x | + |v y -v y | + |v z -v z | = 2.
The graph H k has a regular hexagonal shape, and k is the number of vertices on each edge of the hexagon. Figure 1b shows the triangular grid H 3 . Note that H k appears as a subgraph of H k+1 (where (1, 1, 1) has been added to the coordinates of each vertex in H k ).

An inner vertex v ∈ V (H k ) with coordinates (x, y, z) has 6 neighbors with the following coordinates: (x, y + 1, z + 1), (x -1, y, z + 1), (x -1, y -1, z) , (x, y -1, z -1) , (x + 1, y, z -1) and (x + 1, y + 1, z) (see Figure 1a). We define the line l x=i as the set of vertices {(x, y, z)|x = i} (see Figure 1b). The lines l y=i and l z=i are defined analogously.

One interesting property of the triangular grids is that if we monitor an equilateral triangle with one entire side of the hexagonal border as base, the propagation continues along the border. For example, it suffices to monitor the set 2). We assume throughout the section that k ≥ 4: observe that if k ≤ 3, then

(x + 1, y, z -1) (x + 1, y + 1, z) (x, y + 1, z + 1) (x -1, y, z + 1) (x -1, y -1, z) (x, y -1, z -1) (x, y, z) (a
T = {v = (x, y, z) | 0 ≤ x, y ≤ k -1, k -1 ≤ z ≤ 2k -2} to monitor H k (see Figure
γ P (H k ) = 1 = k 3 , with S = {(k -2, k -2, k -1)} (for k = 2, 3).

Upper bound

We begin by giving a construction for the upper bound:

Lemma 1. For every positive integer k ≥ 4, γ P (H k ) ≤ k 3 .
Proof. Let i = k 3 , and d = k -i -1. Let S be the following set of vertices (see Figure 3):

S = {(1 + 3 , d + , k + d -2 -2 ), 0 ≤ ≤ i -1}. In other words, S contains the vertex v = (1, d, k + d -2
) and vertices whose coordinates are obtained by adding (3, 1, -2) up to i -1 times to the coordinates of v. If k ≡ 0 mod 3, S = S ∪ {(k -1, k -1, k -1)}. Otherwise, S = S . Then we have, depending on the value of k modulo 3:

• k = 3i: |S| = i = 3i 3 . • k = 3i + 1: |S| = i + 1 = 3i+1 3 . • k = 3i + 2: |S| = i + 1 = 3i+2 3 .
In each case, S is a set with cardinality k 3 , and S progressively power dominates first the set T , and thus the whole graph H k . [START_REF] Ferrero | Power domination in honeycomb networks[END_REF][START_REF] Gonçalves | The domination number of grids[END_REF][START_REF] Gonçalves | The domination number of grids[END_REF] (1, 5, 12) (0, 0, 8) (0, 8,

Lower bound

Let A ⊂ V (H k ) be a set of vertices of the graph. We define the border B A ⊆ A of A as the vertices in A with a neighbour not in A:

B A = {v ∈ A, N (v)\A = ∅}.
Let A x=i (resp. A y=i , A z=i ) denote the set of vertices of A in a given line l x=i (resp. l y=i , l z=i ). We define the x-shifted set A x of A as follows (see Figure 4): |A x | = |A|, and for each line l x=i , A x x=i contains the |A x=i | vertices with smallest coordinates y (i.e., the x-shifted set of A contains only left-most vertices on each horizontal line). More formally,

A x x=i = {(x, y, z) | x = i, y = + α, 0 ≤ < |A x=i |}, with α = 0 if 0 ≤ i ≤ k -1, and α = i -(k -1) if k ≤ i ≤ 2k -2.
We define the y-and z-shifted sets of A analogously. Proof. We assume that A is the x-shifted set of A. The proof for the y-shifted and z-shifted sets is symmetric. In this proof, we simplify the notation l x=i into l i . Let a i be the number of vertices in A (and in A ) in line l i , and let b i (resp. b i ) be the number of vertices in B A (resp. B A ) in line l i . We show that b i ≥ b i for every line l i , 0 ≤ i ≤ 2k -2. We consider three cases depending on the value of i (when 0 ≤ i < k -1, when i = k -1 and when k ≤ i ≤ 2k -2):

• 0 ≤ i < k -1: we thus have |l i+1 | = |l i | + 1 and |l i | = |l i-1 | + 1.
Let us consider vertices in line l i which are in A but not in the border of A: there are a i -b i such vertices. By definition, we have a i -b i ≤ a i . Their neighbors (if they exist) in l i-1 and l i+1 are in A. We have thus both

a i -b i ≤ a i+1 -1, and a i -b i ≤ a i-1 . Hence a i -b i ≤ min{a i+1 -1, a i-1 , a i } for 1 ≤ i < k -1 (for i = 0, we have a i -b i ≤ min{a i+1 -1, a i }).
We can apply the same reasoning to the vertices that are in A but not in the border of A : since the vertices of A are consecutive on lines l i-1 , l i and l i+1 , we get that

a i -b i = min{a i+1 -1, a i-1 , a i } (for i = 0, we have a i -b i = min{a i+1 -1, a i }).
Note that the inequalities we get for A turn into equalities on A . Then a i -b i ≤ a i -b i , and thus b i ≥ b i .

• We have a similar proof when k -1 < i ≤ 2k -2, for which we have

|l i+1 | = |l i | -1 and |l i | = |l i-1 | -1: in that case, we get a i -b i = min{a i-1 -1, a i+1 , a i } ≥ a i -b i . • i = k -1: we thus have |l i+1 | = |l i-1 | = |l i | + 1.
As for the previous case, first consider vertices which are in A but not in the border of A:

by definition a i -b i ≤ a i , and we have a i+1 ≥ a i -b i and a

i-1 ≥ a i - b i . Thus a i -b i ≤ min{a i+1 , a i-1 , a i }. Similarly, we get that a i -b i = min{a i+1 , a i-1 , a i }. Thus a i -b i ≤ a i -b i , and so b i ≥ b i .
We define the shifting process of a set A ⊂ V (H k ) as the following iterative process: A +1 = ((A x ) y ) z , with A 0 = A. In other words, we successively apply x-shift, y-shift and z-shift to the set A until a fixed point A * is reached. We show that this fixed point exists and that the resulting set has a particular shape: Lemma 3. (i) The shifting process stops, i.e., there exists * such that

A * +1 = A * . (ii) Let A * = A * . If v ∈ A *
, then all vertices v with v y ≤ v y and v z ≤ v z are also in A * (see Figure 5).

A * Let A be the x-, y-, or z-shifted set of A. We show that if A = A, then w(A ) < w(A).

Recall that for every vertex

v of H k , v x -v y + v z = k -1.
We first show that if v and v are two vertices with v j = v j and v j+1 < v j+1 , then w(v ) < w(v)1 :

• A = A x : v x = v x and v y < v y , so v z = k-1-v x +v y = k-1-v x +v y < v z .
Thus w(v ) < w(v).

• A = A y : v y = v y and v z < v z . Since v x -v y + v z = v x -v y + v z , we get v x + v z = v x + v z . Thus w(v) -w(v ) = v x + 2v y + 2v z -v x -2v y -2v z = v z -v z . So w(v ) < w(v). • A = A z : v z = v z and v x < v x , so v y = v x +v z -k+1 = v x +v z -k+1 ≤ v y . Thus w(v ) < w(v).
Without loss of generality, assume that A is the x-shifted set of A. By definition, for each line l x=i ,

w(A x=i ) -w(A x=i ) = v ∈A \A w(v ) - v∈A\A w(v) ,
and either A x=i = A x=i , and this sums to 0, or A x=i = A x=i , and it is strictly negative. Therefore A = A implies w(A ) < w(A). Since the global weight of any set is always a positive integer, this directly concludes the proof of item (i).

(ii) Let v be a vertex in A * . The vertices

u 1 = (v x + 1, v y , v z -1), u 2 = (v x , v y -1, v z -1) and u 3 = (v x -1, v y -1, v z ) (i.e.
, the north-west, west and south-west neighbors of v) are also in A * : otherwise, we could again shift the set A * and get the set A * -{v} + {u i }, which has less weight than A * , a contradiction. Since this is true for every vertex of A * , the proposition holds.

Recall that M [i] is the set of monitored vertices after i propagation steps.

The key idea of this proof is to consider the size of the sets B M [t] , to bound it and to deduce a bound on |S|. It is a classical way to prove lower bounds for power domination in regular lattices (see for example the lower bound proof on strong products [START_REF] Dorbec | Power domination in product graphs[END_REF]). However, on the contrary to what happens in other cases, the size of the sets B M [t] is not globally bounded from below: at the end of the propagation, no vertices belong to the border of the monitored set. We thus "stop" the propagation in the middle of the process and reason from there.

We first prove the following lemma:

Lemma 4. For any 0 ≤ i ≤ |V (G) \ N [S]|, we have |B M [i] | ≤ 6|S|.
Proof. We prove it by induction on i:

|B M [0] | = |B N [S] | ≤ 6|S| by definition. If the vertex m i+1 becomes monitored by propagation from a vertex v in B M [i] , then v is not in B M [i+1]
, and at most one vertex (m i+1 ) is added to

B M [i+1] . Thus |B M [i+1] | ≤ |B M [i] |.
Using the induction hypothesis, we conclude that

|B M [i+1] | ≤ 6|S|.
We can now prove the lower bound:

Lemma 5. For every positive integer k ≥ 4, γ P (H k ) ≥ 2k -1 6 .
Proof. Let S be a power dominating set of H k . M [i] is the set of monitored vertices from S after i propagation steps.

If

|M [0]| > |V (H k )| 2 = 3k 2 -3k+1 2 , then 7|S| ≥ M [0] > 3k 2 -3k+1 2
, and so

|S| ≥ 3k 2 -3k+1 14 . Since k ≥ 3, |S| ≥ k+1 3 . Thus |S| > k 3 > 2k-1 6
, concluding the proof.

We thus assume that

|M [0]| ≤ |V (H k )| 2 . Let M be the set M [t] containing |V (H k )| 2
vertices, and let M * be the set defined from M by Lemma 3(i). We now prove that

|B M * | >= 2k -1. By Lemma 2, |B M * | ≤ |B M |, hence 2k -1 ≤ |B M |. Using Lemma 4, we get that 2k -1 ≤ |B M | ≤ 6|S|, and so |S| ≥ 2k -1 6
, which will conclude the proof.

We show that for every index 0 ≤ i ≤ 2k -2, the line l v1=i contains at least one vertex of B M * .

Suppose there exists a line l v1=i such that all its vertices are in M * . If 0 ≤ i ≤ k -1, then the vertex w = (i, k + i -1, 2k -2) (i.e., the right-most vertex of the line l x=i ) is in M * , and so by Lemma 3(ii), all vertices of the set {(x, y, z) | y ≤ k + i -1} are also in M * (see Figure 6a). Since k + i -1 > k -1, then strictly more than half of the vertices of H k are in M * , and so M * has strictly more than the required number of vertices, a contradiction. Similarly, if k -1 < i ≤ 2k -2: the vertex w = (i, 2k -2, 3k -3 -i) (i.e., the right-most vertex of the line l x=i ) is in M * , and thus by Lemma 3(ii), all vertices of the set {(x, y, z) | z ≤ 3k -3 -i} are also in M * . Since 3k -3 -i > k -1, then strictly more than half of the vertices of H k are in M * , a contradiction. Thus every line l x=i contains at least one vertex not in M * .

Suppose now that one of the lines l x=i contains no vertex of M * . If 0 ≤ i ≤ k -1 (see Figure 6b), then the vertex w = (i, 0, k -1 -i) (i.e., the left-most vertex of the line l x=i ) is not in M * . By the contrapositive of Lemma 3(ii), the line l z=k-1-i also contains no vertices of M * , and so all vertices of M * are included in the set {(x, y, z) | z < k -1 -i} (they are all on the left and above line l z=k-1-i ). Thus M * contains strictly less than the half of the vertices of

H k , a contradiction. Similarly, if k -1 < i ≤ 2k -2, then the vertex w = (i, i -k + 1, 0) is not in M * .
By the contrapositive of Lemma 3(ii), the line l y=i-k+1 also contains no vertices of M * , and so all vertices of M * are included in the set {(x, y, z) | y < i-k+1} (they are all on the left and below line l y=i-k+1 ). Since in that case i-k +1 < k -1, then again, We thus get that each line l x=i contains at least one vertex of M * and not all its vertices are in M * . Thus each line contains at least one vertex of B M * , and so 2k -1 ≤ |B M * |.

|M * | = |M | < |V (H k )| 2 vertices, a contradiction.
We know that γ P (H k ) is an integer. Since there is no integer between 2k-1 6 = k 3 -1 6 and k 3 , then Lemma 5 directly implies the lower bound:

Lemma 6. For every positive integer k ≥ 4, γ P (H k ) ≥ k 3 .
This, together with Lemma 1, concludes the proof of Theorem 1.

Triangular-shaped border

We now turn to the study of triangular grids with triangular-shaped borders.

A triangular grid with triangular-shaped border

T k has vertex set V (T k ) = {(x, y, z) | x, y, z ∈ [0..k -1], x + y + z = k -1}. Two vertices v and v are adjacent if and only if |v x -v x | + |v y -v y | + |v z -v z | = 2 (
two vertices are adjacent if and only if exactly two of their coordinates differ by 1). Figure 7 shows a representation of T 5 .

x = 0

x = k -1 y = 0 y = k -1 z = 0 z = k -1
Figure 7: The triangular grid T 5 .

We assume throughout this section that k > 4: observe that if k ≤ 4, then γ P (T k ) = 1, with S = {(1, 0, 1)} for k = 2, 3, and S = {(1, 1, 1)} for k = 4. To prove Theorem 2, we first prove the upper bound by giving a construction that achieves it and then prove the lower bound.

Upper bound

Lemma 7. For every positive integer k > 4, γ P (T k ) ≤ k 4 .

Proof. First, note that it is sufficient to monitor the line x = 0 of the grid (i.e., the bottom line) in order to monitor the whole grid. Indeed, the vertex with coordinates (0, k-1, 0) can propagate to the vertex with coordinates (1, k-2, 0), then the one with coordinates (0, k -2, 1) can propagate and so on until the line x = 1 is also monitored. Then we can apply the same method from this line. Let α = k/4 . Let S be the set defined as follows:

S = {v = (x, y, z) | x = 1, y = 1 + 4i, 0 ≤ i < α}. If k ≡ 0 mod 4, then S = S . Otherwise, let S = S ∪ {(1, k -2,
0)} (one can easily check that in that case, the vertex (1, k -2, 0) is not already in the set S ). We then have |S| = k/4 . Then the monitored vertices on the line x = 0 can independently propagate to their non-monitored neighbors (see Figure 8), which allows to monitor the whole graph.

Lower bound

Before proving a matching lower bound, we need to introduce the notions of tip-edges, base-edges and holes of a set M of vertices. Definition 3.1. Let (uv) be an edge of T k such that u and v are in M , and they have a common neighbor w that is not in M . If the triangle (uvw) points in the same direction that the grid T k (i.e., the coordinate common to u and v is increased in w), we say that the edge is a tip-edge of M . Otherwise, or if the edge (uv) is on the border, it is a base-edge of the set M . Remark that some edges can be both tip-and base-edges of M .

A hole of M is a connected component of V \ M that does not contain vertices of the border of the grid. M . We define the quantity Q as follows:

Q(M ) = 2|T (M )| + |B(M )| + 3c(M ) -3h(M ) .
Before proving Lemma 10, we prove two properties of the evolution of the quantity Q during propagation: Lemma 8. Let M [i] be the set of monitored vertices after i propagation steps. Let x be the vertex that propagates at step i and y the one that is newly monitored. We distinguish three cases depending on the position of x and y in the grid (an illustration of all cases can be found in Figures 10, 11 and12):

Then Q(M [i + 1]) ≤ Q(M [i]).

Proof. For sake of clarity, we simplify the notations Q(M [i]), T (M [i]), B(M [i]), c(M [i]) and h(M

1. Vertices x and y are both inner vertices 2. Vertex x is an inner vertex and y is on the border 3. Vertices x and y are both on the border.

Note that since the neighbors of x not adjacent to y need not be taken into account, we do not have to consider the case where x is on the border and y is an inner vertex, which is therefore similar to case 1 or case 3 depending on the position of y.

Case 1. Let x, x 1 , y 1 , y 2 , y 3 , x 2 be the neighbors of y in clockwise order. Since one of the edges (xx 1 ) and (xx 2 ) is a base edge while the other is a tip edge, we assume without loss of generality that (xx 1 ) is the base edge. There are 6 cases, depending on the status of the vertices y 1 , y 2 and y 3 :

1. No vertices y i are in M : then |T | = |T | and |B | = |B|. Thus Q = Q. 2. Vertex y 1 is in M : |T | = |T | -2 and |B | = |B| + 1. Thus Q = Q -3. 3. Vertex y 2 is in M : |T | = |T | + 1, |B | = |B| + 1;
• If y 2 is not in the same connected component of M as x the addition of y to M decreases the number of connected components; thus c = c -1, and so Q = Q. • If y 2 is in the same connected component of M as x the addition of y to M creates a new hole (if either y 1 or y 3 are on the border, there was no hole but there is one after, and otherwise, there was one hole and there are now two). Thus h = h + 1, and so Q = Q.

h = h + 1. Thus Q = Q -6.
Case 2. Let x, x 1 , y 1 , x 2 be the neighbors of y in clockwise order. Without loss of generality, we assume that the edge (xx 1 ) is a base-edge. There are two cases, depending on the status of y 1 : Thus the invariant Q does not increase during propagation.

1. Vertex y 1 is not in M : then |T | = |T |, and |B | = |B|. Thus Q = Q.
Lemma 9. Let S be a set of vertices of a triangular grid T k . Then Q(N [S]) ≤ 12|S|. The edges marked with a "b" or a "t" are base-edges and tip-edges, respectively (note that some are both).

Q(N [S]) = m i=1 Q(N [S i ]
). We prove the result for each connected component and so assume that N [S] is connected.

Let G S = (V S , E S ) be the graph such that V S = S and (xy)

∈ E S if and only if N [x] ∩ N [y] = ∅ and there exist u, u 1 ∈ N [x] and v, v 1 ∈ N [y] such that (uv) ∈ T (N [S]) and (u 1 v 1 ) ∈ B(N [S]
). Thus if x and y are adjacent in G S , then x and y are at graph distance 3 in T k and there are only two possible configurations for u, u 1 , v and v 1 : either u = u 1 and v = v 1 , a situation that we call a bridge, or u is a neighbor of u 1 and v is a neighbor of v 1 , a situation that we call a double-bridge. These situations are illustrated in Figure 13. We now show that the graph G S is planar. From a planar straight-line drawing of T k , we consider the drawing of G S in which the vertices are at the same position as their equivalent in T k and that the segments representing the edge (xy) of G S follow the segments representing the edges of (xu), (uv), (vy) in T k . We now use the term "edge" to refer to the curve representing it.

Suppose that two distinct edges (xy) and (x y ) of G S are crossing each other. Then at least one vertex of {x, u, v, y} coincides with one vertex of {x , u , v , y }: if not, it would mean that the straight-line drawing of T k is not planar, a contradiction. Moreover, vertices {u, v, u , v } are adjacent to nonmonitored vertices and thus do not coincide with one of the vertices {x, y, x , y } for which all neighbors are monitored. Since there is at least one coinciding vertex belonging to the set {u, v, u , v } by definition of the crossing of paths, then at least one coincidence is between a vertex of {u, v} and one of {u , v }.

We show that the two "bridge-like" structures formed by x and y, and x and y can not cross, depending on the type of bridge they form:

• both x and y, and x and y form (simple) bridges: we assume without loss of generality that u coincides with u . Then x coincides with x (it is the only neighbor of u that has all its neighborhood monitored), and v coincides with v (it is the only neighbor of u that is not adjacent to x ). Similarly, y coincides with y . Thus the edges are not distinct in G S , a contradiction.

• one is a simple bridge and the other is a double-bridge: without loss of generality, x and y form a single bridge. Then u and v have two common non-monitored neighbors, and neither of them can coincide with vertices u or v which have only one non-monitored neighbors.

• both x and y, and x and y form a double-bridge: we can consider two cases without loss of generality:

u coincides with u : similarly to the first case, x coincides with x and v with v . Thus v 1 coincides with v 1 . Since y is the only neighbor of v 1 that has all its neighborhood monitored, y coincides with y . Thus the edges (xy) and (x y ) are not distinct in G S , a contradiction. u coincides with v : similarly to the previous cases, y coincides with

x, u coincides with v (it is the neighbor of v adjacent to the nonmonitored neighbor of v but not to y ). Then v 1 coincides with v 1 (it is the monitored common neighbor of u and v ). But v 1 must be adjacent to y, which it is not, a contradiction.

So G S is planar and we can apply Euler's formula to it. Let f (G S ) be the number of internal faces of G S and c(G S ) be the number of connected components of G S ; we have:

|E S | -f (G S ) + 1 = |V S | -c(G S ) .
Note that f (G S ) ≤ h(N [S]). Indeed, each internal face of G S corresponds to a cycle of bridges and double-bridges in the triangular grid; a cycle which contains at least one hole. Note also that |V S | = |S| and c(G S ) ≥ 1, so:

|E S | -h(N [S]) + 2 ≤ |S| .
In the following we will prove that 2|T (N [S])| + |B(N [S])| ≤ 9|S| + 3|E S |, this result and the previous inequality gives:

Q(N [S]) = 2|T (N [S])| + |B(N [S])| + 3c(N [S]) -3h(N [S]) ≤ 9|S| + 3|E S | + 3 -3h(N [S]) ≤ 12|S| -6 ≤ 12|S| .
We now use a discharging method in the graph G to prove that 2|T (N [S])| + |B(N [S])| ≤ 9|S| + 3|E S |, which will conclude the proof. We here consider the graph induced by vertices of N [S] in G.

Initially, we give a charge of 9 to each vertex of S and 3 to each bridge and double bridge (1 to its base-edge and 2 to its tip-edge). We then discharge as follows:

• Each vertex x of S gives a charge of 1.5 to each of its neighbors (keeping a charge of 0 if it is an inner vertex, 3 if it is on the border of the grid and 6 if it is on a corner).

• Each vertex u / ∈ S that has its neighborhood monitored receives 1.5 from its neighbor in S (say x), and gives a charge of 0.5 to each of its common neighbors with x.

• Each vertex incident to a tip-edge that is not part of a bridge or of a double-bridge gives a charge of 1 to this edge. Similarly, a vertex incident to a base-edge that is not part of a bridge or of a double-bridge gives a charge of 0.5 to this edge.

Note that at the end of the process, every tip-edge of S has a charge of 2 and every base-edge of S has a charge of 1. An edge that is both a tip-edge and a base-edge (i.e., a bridge) has charge 3. In the rest of the proof, we consider that the first two discharging steps have been done, and we prove that the last step can be done without creating negative charges on the vertices incident to tip-or base-edges.

Let u be a vertex of N [S] incident to a tip-edge or a base-edge. There are different cases depending on the position of u in the grid (see Figure 14).

Case 1. Suppose that u is an inner vertex. Then it can not be a vertex of S and it has a neighbor x in S, which gave a charge of 1.5 to u. Vertex u also has two common neighbors with x, x 1 and x 2 . It has three other neighbors v 1 , v 2 and v 3 . Without loss of generality, we assume that the neighbors of u are x 1 , v 1 , v 2 , v 3 , x 2 , x in clockwise order and that u and x 1 have the same first coordinate. Since u is the extremity of a tip-edge or a base-edge, at least one of the vertices {v 1 , v 2 , v 3 } is not monitored.

• If none of them are monitored, or if exactly two of them are monitored, then u is the extremity of a tip-edge and a base-edge (that do not form bridges). Since u received a charge of 1.5 from x, it can be discharged and keeps a charge of 0.

• If only v 1 is monitored, then u is the extremity of two base-edges (uv 1 ) and (ux 2 ) that do not form bridges. It can thus be discharged and keeps a charge of 0.5.

• If only v 2 is monitored, then u is the extremity of a tip-edge (ux 1 ), a base-edge (ux 2 ) and of a bridge (uv 2 ). The bridge has already be taken care of in the initial attribution of charges and u can give a charge of 1 to (ux 1 ) and of 0.5 to (ux 2 ), reaching a charge of 0.

• If only v 3 is monitored, then u is the extremity of two tip-edges. The charge it received from x is not sufficient to be discharged. We look at which vertex monitored v 3 . Knowing that v 2 is not monitored, only three vertices could have been in S and monitored v 3 : x 2 and two other neighbors of v 3 that are not in the neighborhood of v 2 , y 1 and y 2 (see Figure 15). If x 2 is in S, then u received a charge of 1.5 from x and of 1.5 from x 2 and has enough charge to give 1 to each tip-edge. If y 2 is in S, then all of the vertices surrounding x 2 are monitored and it gave a charge of 0.5 to u which has a charge of 2 and can be discharged on the two tip-edges. If y 1 is in S, let z be the only vertex in the neighborhood of x 2 that is not in the neighborhood of x nor y 1 . If z is monitored, then x 2 is surrounded and u has enough charge. If z is not monitored, then the edges (uv 3 ) and (x 2 y 2 ) form a double-bridge. So the tip-edge (uv 3 ) has been taken care of in the initial attribution of charge and u can be discharged on the other tip-edge (ux 1 ).

Case 2. Suppose that u is on the border of the grid. If u is in S, it is incident to two base-edges and it has a charge of 3 remaining after the first two steps of discharging. It can be discharged to both edges.

If u is not in S, then it is monitored by a vertex x in S: If x is not on the border, then u has only one neighbor v that is not adjacent to x. If v is not monitored then u is incident to a tip-edge and a base-edge and can be discharged. If v is monitored then u is incident to two base-edges and can be discharged.

If x is on the border, then u has two neighbors v 1 and v 2 that are not adjacent to x, v 1 being on the border. If none of them or both of them are monitored, then u is the extremity of two base-edges and can be discharged. If only v 2 is monitored, then u is the extremity of a tip-edge and a base-edge and can be discharged. If only v 1 is monitored, then (uv 1 ) is a bridge and has been taken care of in the initial attribution.

Case 3. If u is on a corner of the grid, in S or not, then it is the extremity of two base-edges and has enough charge to give.

The initial attribution gives a charge of 9 per vertex of S and of 3 per bridge and double-bridge, so it has a total value of 9|S| + 3|E S |. Since at the end every tip-edge has a charge of 2, every base-edge has a charge of 1 and no vertex has a negative charge, we have 2|T

Conclusion and open questions

We continued the study of power domination in regular lattices, and examined the value of γ P (G) when G is a triangular grid with hexagonal-shaped border or triangular shaped border. We showed that, in the case of hexagonal shape, γ P (G) = k 3 and that, in the case of triangular shape, γ P (G) = k 4 . The process of propagation in power domination led to the development of the concept of propagation radius, i.e., the number of propagation steps necessary in order to monitor the whole graph [START_REF] Dorbec | Generalized power domination: propagation radius and Sierpiński graphs[END_REF]. It would be interesting to study the propagation radius of our constructions and to try and find a power dominating set minimizing this radius.

Also, the relation of our results with the ones presented for hexagonal grids by Ferrero et al. [START_REF] Ferrero | Power domination in honeycomb networks[END_REF] has to be noted: they show (with techniques different from the ones used in this paper) that γ P (G n ) = 2n 3 , where n is the dimension of the hexagonal grid G n , and so γ P (G n ) = γ P (H 2n ). Moreover, it is interesting to remark that G n is an induced subgraph of H 2n . As Dorbec et al. [START_REF] Dorbec | Heredity for generalized power domination[END_REF] showed,

Figure 1 :

 1 Figure 1: (a) The coordinates of the neighbors of an inner vertex v = (x, y, z). (b) The graph H 3 , along with the lines l x=2 and l y=3 .

Figure 2 :

 2 Figure 2: The propagation steps to monitor H 3 once the set T (in the gray area) is monitored. Propagation steps indexed by the same number can be done in parallel.

Figure 3 :

 3 Figure 3: Construction and propagation of the set S on the grid H 9 . In this case, i = 3 and d = 5. Red square-framed vertices are in S , blue circle-framed vertices are in N [S ]. Black vertices are monitored in a first round of parallel propagation steps, gray ones in a second round, and light gray ones in a third round. Observe how the pattern of monitored vertices repeats to monitor the set T in the gray area.

Figure 4 :Lemma 2 .

 42 Figure 4: (Left) Blue-square vertices are in the set A. (Right) Bluesquare vertices are in the x-shifted set A x of A: the left-most vertices of each line l x=i are in A x .

Figure 5 :

 5 Figure 5: The set A * has a staircase shape.

Figure 6 :

 6 Figure 6: (a) If all vertices of a line l x=i are in M * (0 ≤ i ≤ k -1), then all vertices of T k with y ≤ k + i -1 are also in M * . (b) If the line l x=i contains no vertices of M * (1 ≤ i ≤ k -1), then all vertices of M are above and left of line l z=k-i-1 .

Figure 8 :

 8 Figure 8: A minimal power dominating set for the grid T 8 . Red-square vertices are in S and blue-circled vertices are in N [S]. The line x = 0 can be monitored after independent propagation from the monitored vertices on this line, symbolized by the arrows.

Figure 9 :

 9 Figure 9: Examples of tip-edges, base-edges and holes of a set M , depicted in blue.

  [i]) to respectively Q, T , B, c and h, and the notations Q(M [i+ 1]), T (M [i + 1]), B(M [i + 1]), c(M [i + 1]) and h(M [i + 1]) to Q , T , B , c and h , respectively.

4 .

 4 Vertex y 3 is in M : |T | = |T | + 1 and |B | = |B| -2. Thus Q = Q. 5. Vertices y 1 and y 2 or y 1 and y 3 or y 2 and y 3 are in M : then |T | = |T | -1 and |B | = |B| -1. Thus Q = Q -3. 6. All the vertices y i are in M ; then |T | = |T | -3, |B | = |B| -3, and a hole is deleted,

2 .Case 3 .•

 23 Vertex y 1 is in M : then |T | = |T |-2, and |B | = |B|+1. Thus Q = Q-3. Let x, x 1 , y 1 , y 2 be the neighbors of y in clockwise order. There are four cases, depending on the status of vertices y 1 and y 2 : 1. Vertices y 1 and y 2 are not in M : then |T | = |T | -1 and |B | = |B| + 2. Thus Q = Q. 2. Vertices y 1 and y 2 are in M : then |T | = |T | -2 and |B | = |B| + 1. Thus Q = Q -3. 3. Vertex y 1 is in M : then |T | = |T | and |B | = |B|. Thus Q = Q. 4. Vertex y 2 is in M : |T | = |T |, |B | = |B| + 3; If y 2 is in the same connected component of M as x the addition of y to M creates a new hole (containing the vertex y 1 ). Thus h = h + 1 and Q = Q. • If y 2 is not in the same connected component of M as x the addition of y to M decreases the number of connected components of M by one. Thus c = c + 1 and Q = Q.

Figure 10 :

 10 Figure 10: Case 1 of the proof of Lemma 8. Propagation from vertex x to vertex y is shown by the red arrow. Blue-circled vertices are in M , black vertices are not. The edges removed from T (M ) and B(M ) are drawn thicker. The edges added to T (M ) and B(M ) are dashed.The edges marked with a "b" or a "t" are base-edges and tip-edges, respectively (note that some are both).

Figure 11 :

 11 Figure 11: Case 2 of the proof of Lemma 8.

Figure 12 :

 12 Figure 12: Case 3 of the proof of Lemma 8.

Figure 13 :

 13 Figure 13: (a) The edge (uv) is a bridge. (b) The vertices x and y form a double-bridge using edges (uv) and (u 1 v 1 ).

4 .

 4 (N [S])| + |B(N [S])| ≤ 9|S| + 3|E S |. We can now deduce the lower bound on γ P (T k ): Lemma 10. For every positive integer k > 4, γ P (T k ) ≥ k Proof. Let S be a power dominating set of the graph γ P (T k ). By Lemma 9, Q(N [S]) ≤ 12|S|. At the end of the propagation phase, every vertex of the graph is monitored; there are k -1 base-edges on each side of the grid and only one connected component, so Q(V ) = 3(k -1) + 3 = 3k. Since by Lemma 8, Q does not increase during propagation, we have 12|S| ≥ Q(N [S]) ≥ Q(V ) = 3k, and so |S| ≥ k 4 . So γ P (T k ) ≥ k 4 . Combining Lemmas 7 and 10 proves Theorem 2.

Figure 14 :Figure 15 :

 1415 Figure 14: The different cases of the proof of 2|T (N [S])| + |B(N [S])| ≤ 9|S| + 3|E S | in Lemma 9. Squared vertices are in S and monitor the circled vertices. Thicker lines represent the border of the grid.

We here consider that if j = x, then j + 1 = y and j +

= z, and additions are done modulo

the power domination number of an induced subgraph can be either smaller or arbitrarily large compared to the power domination number of the whole graph. It would then be very interesting to investigate further under which conditions induced subgraphs have the same power dominating number as the whole graph.

Research supported in part by NSERC and the GdR-iM of CNRS.