Printer Friendly

Heredity for generalized power domination.

In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for [[gamma].sub.P,k](G - e), [[gamma].sub.P,k](G/e) and for [[gamma].sub.P,k](G - v) in terms of [[gamma].sub.P,k](G), and give examples for which these bounds are tight. We characterize all graphs for which [[gamma].sub.P,k](G - e) = [[gamma].sub.P,k] (G) + 1 for any edge e. We also consider the behaviour of the propagation radius of graphs by similar modifications.

Keywords: power domination, electrical network monitoring, domination, edge critical graphs, propagation radius

1 Introduction

Domination is now a well studied graph parameter, and a classical topic in graph theory. To address the problem of monitoring electrical networks with phasor measurement units (see Baldwin et al. (1993)), power domination was introduced as a variation of the classical domination (see Haynes et al. (2002)). The originality of power domination is the introduction of an additional propagation possibility, relative to the possible use of Kirchhoff 's laws in an electrical network. From this propagation, a vertex can end up to be monitored even though it is at a large distance from any vertex selected to carry a phasor measurement unit. The original status of this new parameter and its applied motivation makes a subject of increasing interest from the community.

All graphs G = (V(G), E(G)) considered are finite and simple, that is, without multiple edges or loops. The open neighbourhood of a vertex v of G, denoted by [N.sub.G](v), is the set of vertices adjacent to v. The closed neighbourhood of v is [N.sub.G] [v] = [N.sub.G](v) U {v}. For a subset S of vertices, the open (resp. closed) neighbourhood [N.sub.G](S) (resp. [N.sub.G][S]) of S is the union of the open (resp. closed) neighbourhoods of its elements. A vertex v in a graph is said to dominate its closed neighbourhood [N.sub.G][v]. A subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of vertices is a dominating set if [N.sub.G] [S] = V(G), that is if every vertex in the graph is dominated by some vertex of S. The minimum size of a dominating set in a graph G is called its domination number, denoted by [gamma](G).

We now define the generalized version of power domination, the case when k =1 coincides with the original power domination. For k-power domination, we define iteratively a set [P.sub.G,k] (S) of vertices monitored by an initial set S (of PMU). The initial set of vertices monitored by S is defined as the set of dominated vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This step is sometimes called the domination step. Then this set is iteratively extended by including the whole neighbourhood of all vertices that are monitored and have at most k non-monitored neighbours. This second part is called the propagation rule. More formally, we define directly the set of monitored vertices for k-power domination following the notation of Chang et al. (2012) :

Definition 1 (Monitored vertices) Let G be a graph, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and k [greater than or equal to] 0. The sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of vertices monitored by S at step i are defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us make some observations about this definition. First, the set of monitored vertices is monotone by inclusion, i.e. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is easy to check by induction, using the fact that whenever [N.sub.G][v] has been included in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it is included in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This also implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is always a union of neighbourhoods. Observe also that if for some integer [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all j [greater than or equal to] [i.sub.0]. We thus denote this set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When the graph G is clear from the context, we simplify the notation to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Definition 2 (k-power dominating set) A set S is a k-power dominating set of G (abbreviated k-PDS) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The least cardinality of such a set is called the k-power domination number of G, denoted by [[gamma].sub.P,k](G). A [[gamma].sub.P,k](G)-set is a k-PDS in G of cardinality [[gamma].sub.P,k] (G).

Observe that k-power domination is also a generalization of domination, that we obtain when we set k = 0. In Chang et al. (2012), the authors showed along with some early results about k-power domination that some bounds, extremal graphs and properties can be expressed for any k, including the case of domination. In Dorbec et al. (2013), a bound from Zhao et al. (2006) on regular graphs is also generalized to any k.

The computational complexity of the power domination problem was considered in various papers (Aazami (2010); Aazami and Stilp (2009); Guo et al. (2008); Haynes et al. (2002)), in which it was proved to be NP-complete on bipartite and chordal graphs as well as for bounded propagation variants. Linear-time algorithms are known for computing minimum k-power dominating sets in trees (Chang et al. (2012)) and in block graphs (Wang et al. (2016)). The problem of characterizing the power domination number of a graph is non trivial for simple families of graphs. Early studies try to characterize it for products of paths/grids Dorfling and Henning (2006); Dorbec et al. (2008) though do not reach complete characterization in a few cases. Other studies propose closed formulas for the power domination number in hexagonal grids (see Ferrero et al. (2011)) or in Sierpinski graphs (see Dorbec and Klavzar (2014)).

In general, it remains difficult to prove lower bounds on the power domination number of a graph. One reason why it is so is that power domination does not behave well when taking subgraphs. In this paper, we explore in detail the behaviour of the power domination number of a graph when small changes are applied to the graph, e.g. removing a vertex or an edge, or contracting an edge. (Recall that the graph obtained by contraction of an edge e = xy, denoted by G/e, is obtained from G - e by replacing x and y by a new vertex [v.sub.xy] (contracted vertex) which is adjacent to all vertices in [N.sub.G-e](x) [union] [N.sub.G-e](y).) In particular, we prove in Section 2 that though the behaviour of the power domination is similar to the domination in the case of the removal of a vertex, the removal of an edge can decrease the power domination number and the contraction of an edge can increase the power domination number, both phenomena that are impossible in usual domination. We characterize the graphs for which the removal of any edge increases the k-power domination number.

Another recent but natural question about power domination is related to the propagation radius. In a graph, a vertex that is arbitrarily far apart from any vertex in the set S may eventually get monitored by S as in the case of paths. However, in the applied circumstances of the monitoring of an electrical network, applying too many times Kirchhoff's laws successively would induce an unreasonable cumulated margin of error. With this consideration in mind, it is natural to consider power domination with bounded time constraints, as was first studied in Aazami (2010), and then in Liao (2016). Inspired by this study, the k-propagation radius of a graph G was introduced in Dorbec and Klavzar (2014) as a way to measure the efficiency of a minimum k-power dominating set (k-PDS). It gives the minimum number of propagation steps required to monitor the entire graph over all [[gamma].sub.P,k](G)-sets.

Definition 3 The radius of a k-PDS S of a graph G is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The k-propagation radius of a graph G as defined in Dorbec and Klavzar (2014) can be expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We finally recall a few graph notations that we use in the following. We denote by [K.sub.n] the complete graph on n vertices, by [K.sub.m,n] the bipartite complete graph with partite sets of order m and n. The path and cycle on n vertices are denoted by [P.sub.n] and [C.sub.n], respectively. For two graphs G and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the Cartesian product of G and H, that is the graph with vertex set V(G) X V(H) and where two vertices (g, h) and (g', h') are adjacent if and only if either g = g' and hh' [member of] E(H), or h = h' and gg' [member of] E(G).

2 Variations on the power domination number

Before considering the different cases of vertex removal, edge removal and edge contraction, we propose the following technical lemma which should prove useful. It states that if two graphs differ only on parts that are already monitored, then propagation in the not yet monitored parts behave the same. For a graph G = (V' E) and two subsets X and Y of V, we denote by [E.sub.G] (X, Y) the set of edges uv [member of] E(G) such that u [member of] X and v [member of] Y. Note that if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains in particular all edges of the induced subgraph G[X] of G on X. All along the rest of the paper, k denotes a positive integer.

Lemma 4 Let G = ([V.sub.G], [E.sub.G]) and H = ([V.sub.H], [E.sub.H]) be two graphs, S a subset of vertices of G and i a non-negative integer. Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the subgraph G' with vertex set [N.sub.G][X] and edge set EG(X,NG[X]).

Suppose there exists a subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that the subgraph H' = ([N.sub.H][Y], [E.sub.H](Y, [N.sub.H][Y])) is isomorphic to G' with a mapping [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that maps X precisely to Y. Then, if for some k-power dominating set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and some integer [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then S is a k-PDS of G and ra[d.sub.P,k](G,S) [less than or equal to] i - j + ra[d.sub.P,k](H, T).

Proof: For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] respectively the sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We prove by induction that for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so it holds for [??] = 0. Now assume that the property is true for some [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose that some vertex v = [phi](u) [member of] [N.sub.H] [Y] satisfies the conditions for propagation in H at step [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We show that u also satisfies the conditions for propagation in G. First, remark that u is monitored at step [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: indeed, if u [member of] X, then by definition of X, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], otherwise if u [member of] X, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and thus by induction, u [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now consider any neighbour u' of u not yet dominated. Then u' [member of] X \ [X.sup.1] and [phi](u') [member of] Y \ [Y.sup.1]. Moreover, by the isomorphism between G' and H', [phi](u') is also adjacent to v, and was among the at most k non monitored neighbours of v in H. Therefore, u has at most k non monitored neighbours in G, and also propagates in G. Applying this statement to all vertices in G', we infer that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By induction, this is also true for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and we deduce that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and thus that S is a k-power dominating set of G and ra[d.sub.P,k](G, S) [less than or equal to] i - j + ra[d.sub.P,k](H, T).

We now use this lemma to state how the k-power domination number of a graph may change with atomic variations of the graph.

2.1 Vertex removal

We denote by G - v the graph obtained from G by removing a vertex v and all its incident edges. Similar to what happens for domination (see Haynes et al. (1998a)), we have the following:

Theorem 5 Let G be a graph and v be a vertex in G. There is no upper bound for [[gamma].sub.P,k](G - v) in terms of [[gamma].sub.P,k] (G). On the other hand, we have [[gamma].sub.P,k] (G - v) [greater than or equal to] [[gamma].sub.P,k] (G) -1. Moreover, if [[gamma].sub.P,k](G - v) = [[gamma].sub.P,k] (G) -1, then ra[d.sub.P,k](G) [less than or equal to] ra[d.sub.P,k](G - v).

Proof: We first prove the lower bound, using Lemma 4. We define H = G - v with the obvious mapping [phi] from V(G) \ v to V(H). Let T be a power dominating set of H = G - v, that induces the minimum propagation radius. Then for the set S = T [union] {v}, the conditions of Lemma 4 hold already from i = 0 and j = 0 and the bound follows. Moreover, we also get that ra[d.sub.P,k](G, S) [less than or equal to] j - i + ra[d.sub.P,k](H, T) = ra[d.sub.P,k] (G - v). For proving there is no upper bound for [[gamma].sub.P,k] (G - v) in terms of [[gamma].sub.P,k] (G), we can consider the star with n leaves [K.sub.1,n], for which the removal of the central vertex increases the k-power domination number from 1 to n

We now describe examples that tighten the lower bound of the above theorem or illustrate better the absence of upper bound (in particular for graphs that remain connected). A first example for which the tightness of the lower bound can be observed is the 4 X 4 grid [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for which we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (see Dorfling and Henning (2006)) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any v. Simple examples for larger k are the graphs [K.sub.k+2,k+2], for which the removal of any vertex drops the k-power domination number from 2 to 1 (those were the only exceptions in Dorbec et al. (2013)), as well as the complete bipartite graph [K.sub.k+3k+3 ]minus a perfect matching.

We now describe infinite families of graphs to illustrate these bounds. The family of graphs [D.sub.k,n] was defined in Chang et al. (2012). It is made of n copies of k + 3-cliques minus an edge, organized into a cycle, and where the end-vertices of the missing edges are linked to the corresponding vertices in the adjacent cliques in the cycle (see Fig. 1). Note that [[gamma].sub.P,k] ([D.sub.k,n]) = n, as each copy of [K.sub.k+3] - e must contain a vertex of a k-power dominating set. Its propagation radius is 1 since [D.sub.k,n] has a dominating set of size n. The removal of an end-vertex of the edges linking two cliques (e.g. u in Fig. 1) does not change its k-power domination number, but the removal of any other vertex (e.g. v in Fig. 1) decreases it by one, and increases the propagation radius from 1 to 2. So this forms an infinite family tightening the lower bound for any value of k and [[gamma].sub.P,k](G).

Now, an infinite family of graphs proving the absence of a upper bound is a generalization [W.sub.k,n] of the wheel (depicted in Fig. 1). It is made of [D.sub.k,n] together with a vertex c adjacent to three vertices of degree k + 2 in one particular clique and to one vertex of degree k + 2 in all the other cliques. Observe that for n [greater than or equal to] k + 2, {c} is the only power dominating set of [W.sub.k,n] of order 1, and thus we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] mod 2). The removal of c induces the graph [D.sub.k,n], increasing the k-power domination number from 1 to n, and dropping the propagation radius from roughly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to 1.

[FIGURE 1 OMITTED]

More constructions could be proposed to show that the propagation radius of a graph can evolve quite freely when a vertex is removed, and there is little hope for other bounds on this parameter when a vertex is removed. The most unlikely example is that the removal of a vertex increase both the k-power domination number and the propagation radius by unbounded value. This is possible with the following variation on [W.sub.k,pn]. Consider pn subgraphs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], all isomorphic to a clique minus an edge, on k + 3 vertices when i = 0 mod p and on k + 1 vertices otherwise. We again connect the end-vertices of the missing edges in the clique into a cycle joining [H.sub.i] to [H.sub.i+i (mod pn)], and add a vertex c adjacent to three vertices of degree k + 2 in all copies [H.sub.i] when i = 0 mod p, and to one vertex of degree k in all the other copies. Then {c} is a k-power dominating set of G inducing a propagation radius of 2. On the other hand, [[gamma].sub.P,k](G - c) = n (one vertex is needed in each Hi, i = 0 mod p) and has propagation radius [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] mod 2).

2.2 Edge removal

In a graph G, removing an edge e can never decrease the domination number. More generally, we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However, the removal of an edge can decrease the k-power domination number as stated in the following result. Indeed, it may happen that the removal of one edge allows the propagation through another edge incident to a common vertex, and thus decreases the power domination number.

Theorem 6 Let G be a graph and e be an edge in G. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We first prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let T be a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If T is also a k-PDS of G - e, then we are done, so assume T is not. Let [j.sub.0] be the smallest integer j such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and let v be a vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists some neighbour u of v in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is also included in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and v cannot be a neighbour of u any more, so e = uv. Thus we choose S = T [union] {v} and using Lemma 4 (with the obvious mapping from G - e to G, and i = j = [j.sub.0]) we get that S is a k-PDS of G - e of order [[gamma].sub.P,k](G) + 1. We also get that if [[gamma].sub.P,k](G - e) = [[gamma].sub.P,k](G) + 1, then ra[d.sub.P,k] (G - e) [less than or equal to] ra[d.sub.P,k] (G).

We now prove that [[gamma].sub.P,k] (G) - 1 [less than or equal to] [[gamma].sub.P,k](G - e). Let T be a minimum k-PDS of H = G - e and u be an end vertex of e. We apply Lemma 4, for S = T [union] {u} and i = j = 0. We get that S is a k-PDS of G and ra[d.sub.P,k](G, S) = ra[d.sub.P,k](G - e, T). We infer that if S is minimal (that is [[gamma].sub.P,k](G) = [Y.sub.P,k](G - e) + 1), then ra[d.sub.P,k](G) [less than or equal to] ra[d.sub.P,k](G - e).

As a first illustration of these possibilities, in the graph G drawn in Fig. 2, the removal of the edge [e.sub.1] decreases the k-power domination number, the removal of the edge [e.sub.3] increases it, and the removal of the edge [e.sub.2] does not have any consequence.

[FIGURE 2 OMITTED]

We now propose a graph family where the removal of an edge decreases the k-power domination number but increases its propagation radius arbitrarily. The graph [G.sub.k,r,a] represented in Fig. 3 satisfies [[gamma].sub.P,k](G) = 2 and ra[d.sub.P,k](G) = a + 2 (which is reached with the initial set {u, v}). If the edge e is removed, we get a new graph whose k-power domination number is 1 and which has propagation radius (r + 3)(a + 1) + 2. So no upper bound can be found for ra[d.sub.P,k](G - e) (in terms of ra[d.sub.P,k](G)) when the removal of an edge decreases the power domination number.

Similar graphs where the edge removal increases the power domination number can also be found. For example, in the graph [G.sub.k,r,a], if we remove the topmost path of length a + 2 from w to v, except for the vertex adjacent to v, we get another graph G' such that {u} is the only [[gamma].sub.P,k](G')-set of order 1, and with ra[d.sub.P,k](G') = (r + 2)(a + 1) + 3. Removing the same edge e, now {u, v} is a minimum [[gamma].sub.P,k](G' - e)-set and ra[d.sub.P,k] (G' - e) = a + 2. This illustrates the fact that no lower bound can be found for ra[d.sub.P,k] (G - e) (in terms of ra[d.sub.P,k](G)) when the removal of an edge increases the power domination number.

We now characterize the graphs for which the removal of any edge increases the power domination number. Define a k-generalized spider as a tree with at most one vertex of degree k + 2 or more. See Fig. 4 for an example.

[FIGURE 3 OMITTED]

Theorem 7 Let G be a graph. For each edge e in G, [[gamma].sub.P,k](G - e) > [[gamma].sub.P,k](G) if and only if G is a disjoint union of k-generalized spiders.

Proof:

First observe that if G is a disjoint union of k-generalized spiders, then its k-power domination number is exactly its number of components, and clearly [[gamma].sub.P,k](G - e) > [[gamma].sub.P,k](G) for any edge e in G.

Let G be a graph and let S be a [[gamma].sub.P,k](G)-set. We label the vertices of G with integers from 1 to n and consider the subsequent natural ordering on the vertices. For i [greater than or equal to] 0, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the minima are taken according to the ordering of the vertices. Let E' be the union of all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i [greater than or equal to] 0. If we consider the edges of E' as defined above oriented from u to v, then the in-degree of each vertex not in S is 1, of vertices in S is 0. Also the graph is acyclic, and each vertex not in S has out-degree at most k. Thus the graph induced by E' is a forest of k-generalized spiders. Note also that S is a k-PDS of this graph. We now assume that for any edge e G E(G), [[gamma].sub.P,k](G - e) > [[gamma].sub.P,k](G), and we then prove that E' = E(G).

By way of contradiction, suppose there exists an edge e in E(G) and not in E'. We prove that S is a k-PDS of G - e. For that, we prove by induction that for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. First observe that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Indeed, suppose there exists a vertex x in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] but not in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then e has to be of the form xv with v [member of] S. But since e [??] [E'.sub.0], there exists another vertex u < v in S such that ux [member of] [E'.sub.0], and x [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Assume now [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some i [greater than or equal to] 0, and let us prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let x be a vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then by induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there exists a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose e [not equal to] xv. Then, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and by induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If e = xv then by the choice of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], there exists a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then by induction hypothesis, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore E(G) = E' and G is indeed a union of k-generalized spiders.

[FIGURE 4 OMITTED]

Observe that there also exist graphs for which the removal of any edge decreases the power domination number, though we did not manage to characterize them. The simplest example is the complete bipartite graph [K.sub.k+2k+2], in which the removal of any edge decreases the k-power domination number from 2 to 1. This graph already played a noticeable role among the k + 2-regular graphs, as observed in Dorbec et al. (2013). Another example is the graph [K.sub.k+3,k+3] - M, where M is a perfect matching, in which we have [[gamma].sub.P,k] ([K.sub.k+3,k+3] - M) = 2 and [[gamma].sub.P,k]( ([K.sub.k+3jk+3] - M) - e) = 1 for any edge e. More complex examples are the Cartesian product of [K.sub.4] and [W.sub.5], where the k-power domination number decreases from 3 to 2. A general family of graphs having this property is the Cartesian product of two complete graphs of the same order [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which shall be described in Section 2.4.

2.3 Edge contraction

Contracting an edge in a graph may decrease its domination number by one, but cannot increase it (see Huang and Xu (2012)). As we prove in the following, increasing of the power domination number may occur.

Theorem 8 Let G be a graph and e be an edge in G. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Let e = xy be an arbitrary edge in G, we denote by [v.sub.xy] the vertex obtained by contraction of e in G/e. We first prove that [[gamma].sub.P,k](G/e) [greater than or equal to] [[gamma].sub.P,k](G) - 1. Let T be a minimum k-PDS of H = G/e. Suppose first that the vertex [v.sub.xy] [member of] T, then taking S = T {[v.sub.xy]} [union] {x, y}, the conditions of Lemma 4 hold from i = j = 0 with the natural mapping from G \ {x, y} to H \ [v.sub.xy]. We infer that S is a k-PDS of G and ra[d.sub.P,k](G, S) = ra[d.sub.P,k](G/e, T). We now consider the case when [v.sub.xy] [??] T. Let [j.sub.0] be the smallest j such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let w be a neighbour of [v.sub.xy] that brought [v.sub.xy] into [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], w is a neighbour of [v.sub.xy] in T, otherwise when [j.sub.0] > 0, w is a neighbour of [v.sub.xy] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By definition of edge contraction, the edge w[v.sub.xy] corresponds to an edge wx or wy in E(G). If wx [member of] E(G), then take S = T [union] {y}, otherwise take S = T [union] {x}. Then, applying Lemma 4 (with the natural mapping from G \ {x, y} to H \ [v.sub.xy] and i = j = [j.sub.0]), we get that S is a k-PDS of G and ra[d.sub.P,k](G,S) = ra[d.sub.P,k](G/e, T). This implies that if [[gamma].sub.P,k](G) = [[gamma].sub.P,k](G/e) + 1, then ra[d.sub.P,k](G) [less than or equal to] ra[d.sub.P,k](G/e).

We now prove that [[gamma].sub.P,k](G/e) [less than or equal to] [[gamma].sub.P,k](G) + 1. Let T be a minimum k-PDS of G and let S = T\{x,y}[union] {[v.sub.xy]}. Let [j.sub.0] be the smallest j such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Here also, we can use Lemma 4 (with the natural mapping from (G/e) \ [v.sub.xy] to G \ {x, y} and i = j = [j.sub.0]), and get that S is k-PDS of G/e. We also get that if [[gamma].sub.P,k](G/e) = [[gamma].sub.P,k] (G) + 1, then ra[d.sub.P,k](G/e) [greater than or equal to] ra[d.sub.P,k](G).

The bounds in Theorem 8 are tight. For example, the lower bound holds for the graphs [K.sub.k+2,k+2] and [K.sub.k+3,k+3 ]- M, where M is a perfect matching, but also for the Cartesian product of two complete graphs of same order [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as is described in the next section. The upper bound is attained for example for the k-generalized spider T in Fig. 4, which satisfy [[gamma].sub.P,k](T) = 1 and [[gamma].sub.P,k](T/[a.sub.1][b.sub.1]) =2 for k [greater than or equal to] 2.

2.4 On the Cartesian product of twin complete graphs

The Cartesian product of two complete graphs of same (large enough) order is such that removing a vertex, removing an edge or contracting an edge decrease its power domination number. We here prove these properties.

Observation 9 Let a [greater than or equal to] 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Denote by {[v.sub.1,]..., [v.sub.a]} the vertices of [K.sub.a]. If a < k + 2, then any vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a minimum k-PDS. Now, assume a [greater than or equal to] k + 2. Let S = {([v.sub.i], [v.sub.i]) | 1 [less than or equal to] i [less than or equal to] a - k}. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the set of vertices A = {([v.sub.i], [v.sub.i]) | a - k + 1 [less than or equal to] i, j [less than or equal to] a} is yet to be monitored. Since any vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has either 0 or k neighbours in A and each vertex in A is adjacent to some vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] covers the whole graph. Thus S is a k-PDS of G. Therefore, [[gamma].sub.P,k](G) [less than or equal to] a - k.

We now prove that [[gamma].sub.P,k](G) [greater than or equal to] a - k. By way of contradiction, suppose S is a k-PDS of G such that | S | [less than or equal to] a - k - 1. Without loss of generality, assume that the elements of S belong to the first a - k - 1 columns and rows of G. Then the vertices in the set B = {([v.sub.i,] [v.sub.i]) | a - k [less than or equal to] i, j [less than or equal to] a} are not adjacent to any vertex in S, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since any vertex in G \ B has either 0 or k +1 neighbours in B, no vertices from this set may get monitored later on, a contradiction.

Observation 10 Let a [greater than or equal to] k + 2 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [[gamma].sub.P,k](G - v) = a - k - 1 for any vertex v in V(G).

Proof: Denote by {[v.sub.1,]..., [v.sub.a]} the vertices of [K.sub.a]. We prove the result for v = ([v.sub.1], [v.sub.1]) which implies the result for any v by vertex transitivity. First observe that S = {([v.sub.i], [v.sub.i]) | 2 [less than or equal to] i [less than or equal to] a - k} is a k-PDS of G - v. Indeed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then vertices ([v.sub.i], [v.sub.i]) (resp. ([v.sub.i], [v.sub.i])) with 2 [less than or equal to] i [less than or equal to] a - k have only vertices ([v.sub.j], [v.sub.1]) (resp. ([v.sub.1], [v.sub.j])) with a - k +1 [less than or equal to] j [less than or equal to] a as unmonitored neighbours, which are thus all in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The next propagation step covers the graph. Thus S is a k-PDS of G - v and [[gamma].sub.P,k] (G - v) [less than or equal to] a - k - 1. Now by Theorem 5 and Observation 9, [[gamma].sub.P,k](G - v) [greater than or equal to] a - k - 1.

Observation 11 Let a [greater than or equal to] k + 2 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [[gamma].sub.P,k](G - e) = a - k - 1 for any edge e in E(G).

Proof: Denote by {[v.sub.1],..., [v.sub.a]} the vertices of [K.sub.a]. By edge transitivity of G, we can assume that e = ([v.sub.1], [v.sub.1])([v.sub.2], [v.sub.1]). Let S = {([v.sub.i],[v.sub.j]) | 2 [less than or equal to] i [less than or equal to] a - k}. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now the vertex ([v.sub.2], [v.sub.1]) has only k unmonitored neighbours, namely the vertices ([v.sub.j], [v.sub.1]) for a - k < j [less than or equal to] a, and they all are in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then all vertices ([v.sub.j],[v.sub.2]) for a - k < j [less than or equal to] a have only k unmonitored neighbours and thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains all vertices ([v.sub.i], [v.sub.j]) for i [greater than or equal to] 2. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains the whole graph and [[gamma].sub.P,k](G - e) [less than or equal to] a - k - 1. The lower bound follows from Theorem 6 and Observation 9.

Observation 12 Let a [greater than or equal to] k + 2 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [[gamma].sub.P,k] (G/e) = a - k - 1 for any edge e in E(G).

Proof: Denote by {[v.sub.1],..., [v.sub.a]} the vertices of [K.sub.a]. By edge transitivity of G, we can assume that e = ([v.sub.1], [v.sub.1])([v.sub.2], [v.sub.1]) and we denote by [v.sub.e] the vertex in G/e obtained by contracting ([v.sub.1], [v.sub.1]) and ([v.sub.2], [v.sub.1]). Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains all vertices ([v.sub.1], [v.sub.j]) with 1 [less than or equal to] i [less than or equal to] a - k and 1 [less than or equal to] j [less than or equal to] a. After one propagation step, the whole graph is monitored so [[gamma].sub.P,k](G/e) [greater than or equal to] a - k - 1. The lower bound follows from Theorem 8 and Observation 9

Acknowledgements

The authors thank the Erudite programme of the Kerala State Higher Education Council, Government of Kerala, India for funding the visit of the first author during March 2014. The second author is supported by Maulana Azad National Fellowship (F1-17.1/2012-13/MANF-2012- 13-CHR-KER-15793) of the University Grants Commission, India.

References

A. Aazami. Domination in graphs with bounded propagation: algorithms, formulations and hardness results. J. Comb. Optim., 19(4):429-456, 2010.

A. Aazami and K. Stilp. Approximation algorithms and hardness for domination with propagation. SIAM J. Discrete Math., 23(3):1382-1399, 2009.

T. Baldwin, L. Mili, M. Boisen Jr, and R. Adapa. Power system observability with minimal phasor measurement placement. IEEE Trans. Power Systems, 8(2):707-715, 1993.

G. J. Chang, P. Dorbec, M. Montassier, and A. Raspaud. Generalized power domination of graphs. Discrete Appl. Math., 160(12):1691-1698, 2012.

P. Dorbec and S. Klavzar. Generalized power domination: propagation radius and Sierpmski graphs. Acta Appl. Math., 134:75-86, 2014.

P. Dorbec, M. Mollard, S. Klavzar, and S. Spacapan. Power domination in product graphs. SIAM J. Discrete Math., 22(2):554-567, 2008.

P. Dorbec, M. A. Henning, C. Lowenstein, M. Montassier, and A. Raspaud. Generalized power domination in regular graphs. SIAM J. Discrete Math., 27(3):1559-1574, 2013.

M. Dorfling and M. A. Henning. A note on power domination in grid graphs. Discrete Appl. Math., 154(6): 1023-1027, 2006.

D. Ferrero, S. Varghese, and A. Vijayakumar. Power domination in honeycomb networks. J. Discrete Math. Sci. Cryptogr., 14(6):521-529, 2011.

J. Guo, R. Niedermeier, and D. Raible. Improved algorithms and complexity results for power domination in graphs. Algorithmica, 52(2):177-202, 2008.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of domination in graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1998a.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Domination in Graphs: Advanced Topics. Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1998b.

T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning. Domination in graphs applied to electric power networks. SIAM J. Discrete Math., 15(4):519-529, 2002.

J. Huang and J.-M. Xu. Note on conjectures of bondage numbers of planar graphs. Appl. Math. Sci. (Ruse), 6(65-68):3277-3287, 2012.

C.-S. Liao. Power domination with bounded time constraints. J. Comb. Optim., 31(2):725-742, 2016.

C. Wang, L. Chen, andC. Lu. k-Power domination in block graphs. J. Comb. Optim., 31(2):865-873, 2016.

M. Zhao, L. Kang, and G. J. Chang. Power domination in graphs. Discrete Math., 306(15):1812-1816, 2006.

Paul Dorbec (1,2)

Seethu Varghese (3)

A. Vijayakumar (3)

(1) Univ. Bordeaux, LaBRI, France

(2) CNRS, LaBRI, France

(3) Department of Mathematics, Cochin University of Science and Technology, India

received 2nd Oct. 2015, revised 22nd Feb. 2016, accepted 17th Mar. 2016.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dorbec, Paul; Varghese, Seethu; Vijayakumar, A.
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Nov 1, 2016
Words:6840
Previous Article:Stokes posets and serpent nests.
Next Article:Sequential selection of the [kappa] best out of n rankable objects.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters