# Open k-monopolies in graphs: complexity and related concepts.

Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open k-monopolies in graphs which are closely related to different parameters in graphs. Given a graph G = (V, E) and X [??] V, if [[delta].sub.x] (v) is the number of neighbors v has in X, k is an integer and t is a positive integer, then we establish in this article a connection between the following three concepts:* Given a nonempty set M [??] V a vertex v of G is said to be k-controlled by M if [[delta].sub.M](v) [greater than or equal to] [[delta].sub.V](v)/2+ k. The set M is called an open k-monopoly for G if it k-controls every vertex v of G.

* A function f : V [right arrow] {-1,1} is called a signed total t-dominating function for G if f (N(v)) = [[summation].sub.v[member of]N(v)] f (v) [greater than or equal to] t for all v [member of] V.

* A nonempty set S [??] V is a global (defensive and offensive) k-alliance in G if [[delta].sub.s] (v) [greater than or equal to] [[delta].sub.V-S](v) + k holds for every v [member of] V.

In this article we prove that the problem of computing the minimum cardinality of an open 0-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs. In addition we present some general bounds for the minimum cardinality of open k-monopolies and we derive some exact values.

Keywords: open k-monopolies, k-signed total domination, global defensive k-alliance, global offensive k-alliance

1 Introduction

We begin stating some terminology and notation which we will use. Throughout this article, G denotes a simple graph with vertex set V (G) and edge set E(G) (we will use only V and E if the graph is clear from the context). The order of G is n = |V (G)| and the size is m = |E(G)|. We denote two adjacent vertices u and v by u ~ v. Given a vertex v [member of] V, the set N (v) = {u [member of] V : u ~ v} is the open neighborhood of v, and the set N [v] = N (v) [union] {v} is the closed neighborhood of v. So, the degree of a vertex v [member of] V is [delta](v) = |N (v)|. Given a set S [subset] V, the open neighborhood of S is N (S) =[[union].sub.v[member of] S] N (v) and the closed neighborhood of S is N [S] = N (S) [union] S. The minimum and maximum degree of G are denoted by [delta](G) and [DELTA](G), respectively (again we use [delta] and [DELTA] for short if G is clear from the context). For a nonempty set S [??] V and a vertex v [member of] V, [N.sub.s](v) denotes the set of neighbors v has in S,i.e., [N.sub.s](v) = S[intersection] N(v). The degree of v in S will be denoted by [[delta].sub.s](v) = |[N.sub.s](v)|. Also, [??] = V - S is the complement of a set S in V and [partial derivative]S = N [S] - S is the boundary of a set S. The subgraph of G induced by a set S is denoted by [??].

In the first article, see Linial et al. (1993), on closed monopolies in graphs (called monopolies there) the following terminology was used. A vertex v in G is said to be controlled by a set M [subset] V if at least half of its closed neighborhood is in M. The set M is called a closed monopoly if it controls every vertex v of G. Equivalently, the set M is a closed monopoly in G, if for any vertex v [member of] V(G) it follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this article, we introduce open k-monopolies in a natural way, by replacing closed neighborhoods with open neighborhoods. Hence, we can use the degree of vertices instead of cardinalities of closed neighborhoods. Given some integer k, a vertex v of G is said to be k-controlled by a set M if [[delta].sub.M](v) [greater than or equal to] [delta](v)/2 + k. Analogously, the set M is called an open k-monopoly if it k-controls every vertex v of G. Notice that not for every value of k there exists an open k-monopoly in G (further on we give some suitable interval for such k). Also, note that, close and open monopolies cannot be exactly compared, since in a closed monopoly a vertex v also counts itself in controlling v, which is not the case in any open monopoly. The smallest example is already [K.sub.2], where is only one vertex in a closed monopoly, but both vertices are necessary in an open 0-monopoly. Differently, there are only two vertices in a minimum open 0-monopoly of [P.sub.5], while we need at least three vertices in every closed monopoly of [P.sub.5]. In this article, we are focused only in open k-monopolies. In this sense, from now on we omit the term "open" and just use the terminology of k-monopolies. On the other hand, we remain using the term closed monopoly whenever referring to some previous work on this topic.

According to Bermond et al. (2003), several problems related to overcoming failures have some common approaches around the notion of majorities. Their ideas are directed toward decreasing, as much as possible, the damage caused due to failed vertices; by maintaining copies of the most important data and performing a voting process among the participating processors in situation that failures occur; and by adopting as true those data stored at the majority of the not failed processors. This idea is also commonly used in some fault tolerant algorithms including agreement and consensus problems (see Dwork et al. (1988)), diagnosis problems (see Sullivan (1986)) or voting systems (see Garcia-Molina and Barbara (1985)), among other applications and references.

Bermond et al. (2003) were interested into locality based on the following facts. Frequently, processors running in a system are better aware of whatever happens in their neighborhood than outside of it. Moreover, some distributed network models allow only for computations developed with local processors, which means that, a processor can only obtain a data from other processors having a "relative" close distance from itself. Therefore, it is more efficient to store data as locally as possible.

Nevertheless, there could exists also a risk in this way. If the voting is restricted to local neighborhoods, we could produce a sufficiently large set of failures which will probably constitute the majority in some of these neighborhoods. In this sense, see Bermond et al. (2003), the authors assert the following: once the voting is performed over subsets of vertices, the ability of failed vertices to influence the outcome of the votes becomes not only a function of their number but also a function of their location in the network: well situated vertices can acquire greater influence. This simple fact led them to study the problem of characterizing the potential power of a set of failures in a network of processors, and as a consequence, the study of (closed) monopolies in graphs.

Notions of closed monopolies in graphs were introduced first by Linial et al. (1993), where several ideas regarding voting systems were described. Once such article appeared, a high number of researches were devoted to such parameter and its relationship with other similar structures like (defensive and offensive) alliances, see Kristiansen et al. (2004), or signed dominating functions, see Dunbar et al. (1995), among other works. An interesting article, where several of these connections are dealt with, is from Fernau and Rodriguez-Velazquez (2014). Moreover, this article presents a possible generalization of all these (closed) monopolies-related structures which comprise them altogether. The complexity of closed monopolies in graphs is also well studied. The NP-hardness of finding the minimum cardinality of a closed monopoly in a graph is easy to observe as stated by Linial et al. (1993). In such work was also pointed out a conjecture concerning the inapproximability of such problem. A weaker version of such conjecture has been proved by Mishra et al. (2002). In addition some other inapproximability results of this problem have appeared by Mishra (2012) and Mishra and Rao (2006). Particularly, in Mishra and Rao (2006), these results are centered in regular graphs. Moreover, there it is also proved that for the case of tree graphs, a closed monopoly of minimum cardinality can be computed in linear time. On the other hand, see Khoshkhah et al. (2013), some relationships and bounds for the minimum cardinality of closed monopolies in graphs are stated in terms of matchings and/or girths. Also, dynamic closed monopolies has been introduced in connection with modeling some problems of spreading the influence in social networks (see Bermond et al. (2003); Peleg (2002)). Other studies in dynamic closed monopolies can be found in Flocchini et al. (2003) and in Zaker (2012).

2 Concepts related to monopolies

Many times mathematical concepts are defined independently in two or even more papers. When this occurs, the equivalence sometimes is obvious (mostly when papers occur in the same time period), but sometimes we need more effort to find the connection (mostly when there is a longer time period between publications). This may yield not sufficient effort of later authors with the history, but we rather present it as an enough important concept to start to investigate it from different point of view.

The above holds (at least partial) for signed (total) domination (introduced first by Hattingh et al. (1995) (by Zelinka (2001))) and for different types of alliances (introduced first by Kristiansen et al. (2004)). We add monopolies to this list and present these connections in this section.

2.1 Alliances

Alliances in graphs were introduced first by Kristiansen et al. (2004) and generalized to k-alliances by Shafique and Dutton (2003, 2006). After that several works have been developed in this topic. Remarkable cases are Favaron et al. (2004) and Haynes et al. (2003). Relationships with different parameters of the graphs have been obtained and the alliances of several families of graphs have been studied. A nonempty set S [??] V is a defensive k-alliance in G for k [member of] {-[DELTA],...,[DELTA]} if for every v [member of] S

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

Moreover, for k [member of] {2 - [DELTA],...,[DELTA]}, a nonempty set S [??] V is an offensive k-alliance in G if for every v [member of] [partial derivative]S

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

A nonempty set S [??] V is a powerful k-alliance if S is a defensive k-alliance and an offensive (k + 2)-alliance. A set D is a dominating set in G if every vertex outside of D is adjacent to at least one vertex of G.

A (defensive, offensive or powerful) k-alliance is called global if it is a dominating set. The global defensive (offensive) k-alliance number of G, denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is defined as the minimum cardinality of a global defensive (offensive) k-alliance in G. For k [member of] {-[DELTA],...,[DELTA] - 2}, the global powerful k-alliance number of G, denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is defined as the minimum cardinality of a global powerful k-alliance in G. A global powerful alliance of minimum cardinality in G is called a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](G)-set of G. Notice that there exist graphs not containing any global powerful k-alliance for some specific values of k. In this sense, in this work we are interested in those graphs having global powerful k-alliances. It means that whenever we study such an alliances we are supposing that the graph contains it.

Notice that the terminology used for alliances provides a very useful tool which can be used while proving several results, i.e., a set of vertices M is a k-monopoly in G if and only if for every vertex v of G, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (from now we will call this expression the k-monopoly condition) and we will say that M is a k-monopoly in G if and only if every v of G satisfies the k-monopoly condition for M.

An interesting possible generalization of alliances in graphs (and some other related parameters) is given by Fernau and Rodriguez-Velazquez (2014). In this work is proposed a new framework, which the authors call (D, O)-alliances. The main idea of this allows not only to characterize several known variants of alliances, but also suggest a unifying framework for its study. In this sense, a (D, O) -alliance, with D,O [??] Z in a graph G = (V, E) is a set S such that for any v [member of] S, [[delta].sub.s](v) -[??] [member of] D and for any v [member of] N(S) \ S, [[delta].sub.s](v) - [??] [member of] O. According to this, it is clear to observe that a defensive k-alliance can be understood as a ({z [member of] [??] : z [GREATER THAN OR EQUAL TO] k}, [??])-alliance, and an offensive k-alliance as a ([??], {z [member of] [??] : z [GREATER THAN OR EQUAL TO] k})-alliance.

2.2 Signed (total) domination

Givenagraph G = (V, E) andafunction f : V [RIGHT ARROW] {-1,1} we consider the following for f :

* f is a signed dominating function for G if f (N[v]) = [[summation].sub.v[member of]N][v] f (v) [GREATER THAN OR EQUAL TO] 1, for all v [member of] V.

* f is a signed total dominating function for G if f (N (v)) = [[summation].sub.v[member of]N(v)] f (u) [GREATER THAN OR EQUAL TO] 1, for all v [member of] V.

* f is a signed k -dominating function for G if f (N [v]) [GREATER THAN OR EQUAL TO] k for all v [member of] V.

* f isa signed total k -dominating function for G if f (N (v)) [GREATER THAN OR EQUAL TO] k for all v [member of] V.

The minimum weight [[summation].sub.v[member of]V] f (v) of a signed (total) (k-dominating) dominating function f is the signed (total) (k -domination) number of G and they are denoted in the following way.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Notice that, if k = 1, then a signed (total) 1 -dominating function is a standard signed (total) dominating function for G. Also, any kind of signed (total) (k-dominating) dominating function f of G induces two disjoint sets of vertices [B.sub.1] and [B.sub.-1], such that for every vertex v [member of] [B.sub.i], f (v) = i with i [member of] {-1,1}. Hereby we will represent such a function f by the sets [B.sub.1] and [B.sub.-1] induced by f and we will write f = ([B.sub.1],[B.sub.-1]). A signed (total) (k-dominating) dominating function f of minimum weight is called a Y-function with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively.

2.3 Connections between concepts

Observing the definitions of monopoly and alliance we see that both concepts are closely related. That is, let M be a 0-monopoly in G = (V, E) and let v [member of] V. Hence, v has at least half of its neighbors in M, i.e., [[delta].sub.M](v) [greater than or equal to] [delta](v)/2, which leads to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since this is satisfied for every vertex of G we obtain that M is a global defensive 0-alliance and also a global offensive 0-alliance. On the contrary, let A be a global defensive 0-alliance which is also a global offensive 0-alliance in G. Hence, for every vertex v [member of] V we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which leads to [[delta].sub.A](v) [greater than or equal to] [delta](v)/2. Therefore, A is a 0-monopoly.

Shafique and Dutton (2003) defined the concept of global powerful k-alliances. Nevertheless, it was not taken into account the possibility of studying the cases in which a set is a global defensive k-alliance and also a global offensive k-alliance. According to the concept of monopoly we observe the importance of such a case, which is one of our motivations to develop the present investigation.

We continue with a relationship between signed total domination, alliances and monopolies.

Theorem 1. Let G = (V, E) be a graph and let k [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an integer. The following statements are equivalent:

(i) M [subset] V is a k-monopolyin G;

(ii) M is a global defensive (2k) -alliance and a global offensive (2k) -alliance in G;

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed total (2k)-dominating function for G. Moreover, if k = 0, then (i) and (ii) are also equivalent.

Proof: The equivalence between (i) and (ii) is straightforward since for every set of vertices M and every vertex v of G, the conditions [[delta].sub.M(v)] [greater than or equal to] [delta](v)/2 +k and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are equivalent for every [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let M be a global defensive (2k)-alliance and a global offensive (2k)-alliance in G. Let the function f : V [right arrow]* {-1,1} be such that for any v [member of] V, it follows f (v) = 1 if v [member of] M and, f (v) = -1 otherwise. If v [member of] M, then since M is a global defensive (2k)-alliance in G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, if v [member of] [??], then by using that M is a global offensive (2k)-alliance in G, the same computation as above gives that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed total (2k)-dominating function for G.

On the other hand, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a signed total (2k)-dominatingfunctionfor G. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let the vertex u [member of] V .If u [member of] M', then since f' is a signed total (2k)-dominating function in G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, M' is a global defensive (2k)-alliance in G. Finally, since f' is a signed total (2k)-dominating function for G, if u [member of] [bar.M'], then as above we deduce that M' is a global offensive (2k)-alliance. * The following corollary is a direct consequence of Theorem 1 (ii) and (iii). We omit the proof.

Corollary 2. Let G = (V, E) be a graph and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an integer. A set M [subset] V is a global defensive k-alliance and a global offensive k-alliance in G if and only if f = ([B.sub.1] = M, [B.sub.-1] = [bar.M]) is a signed total k-dominating function for G.

Now we prove a connection between signed domination and powerful alliances. Theorem 3. Let G = (V, E) be a graph and let k [member of] {0,..., [delta](G)}. Then S [subset] V is a global powerful k-alliance in G if and only if f = {[B.sub.1] = S,[B.sub.-1] = [??]) is a signed (k + 1) -dominating function for G.

Proof: Let S be a global powerful k-alliance in G. So, S is a global defensive k-alliance and a global offensive (k + 2)-alliance in G. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a function in G and let v [member of] V. We consider the following cases.

Case 1: v [member of] S. Since S is a global defensive k-alliance in G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Case 2: v [member of] [bar.S]. Since S is a global offensive (k + 2)-alliance in G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed (k + 1)-dominating function for G. On the other hand, let f ' = ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) be a signed (k + 1)-dominating function in G. We will show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a global powerful k-alliance in G. Let u [member of] V. We consider the following.

Case 3 : u [member of] A. Since f' is a signed (k + l)-dominating function for G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, A is a global defensive k-alliance in G.

Case 4: u [member of] [bar.A]. Since A is a signed (k + 1)-dominating function in G, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, A is a global offensive (k + 2)-alliance and, as a consequence, A is a global powerful k-alliance in G. Therefore, the proof is complete. []

Corollary 4. For any graph G of order n and any integer k [member of] {0,..., [delta](G)},

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let S be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](G)-set. By Theorem 3, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed total (k + 1)- dominating function of minimum weight in G. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the result follows by adding these two equalities above. []

According to the above ideas we can resume the relationships which motivated our work in the following table.

k-monopoly (k [greater than or equal to] 0) [??] k-monopoly (k [greater than or equal to] 1) [??] Signed total k-domination (k [greater than or equal to] 1) [??] Signed (k + 1)-domination (k [greater than or equal to] 0) [??] k-monopoly (k Global defensive (2k)-alliance and [greater than or equal to] 0) global offensive (2k)-alliance k-monopoly Signed total (2k)-domination (k [greater than or equal to] 1) Signed total k-domination (k Global defensive k-alliance and [greater than or equal to] 1) global offensive k-alliance Signed (k + 1)-domination Global defensive k-alliance and (k [greater than or equal to] 0) global offensive (k + 2)-alliance (A global powerful k-alliance)

Notice that the definition of signed (total) k-dominating function is restricted to k [greater than or equal to] 1 while k-alliances are defined for any k [member of] {-[DELTA](G),..., [DELTA](G)} and k-monopolies can be defined for some integer k whose limits are presented further. In this sense, these concepts being quite similar between them could be generalized for k being zero or negative. To obtain a meaningful negative lower bound for k-monopolies we involve another well-known concept: total domination(i). Namely, every k-monopoly, k [greater than or equal to] 0 is also a total dominating set for G. To remain this property also for k < 0, we need to demand [[delta].sub.M](v) [greater than or equal to] 1 for every v [member of] V(G). Therefore in this work we propose the following definition of monopolies and we study some of its mathematical properties.

Given a integer k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a set M, a vertex v of G is said to be k-controlled by M if [[DELTA].sub.M](V) [greater than or equal to] [delta](v)/2 +k. The set M is called a k-monopoly if it k-controls every vertex v of G. The minimum cardinality of any k-monopoly is the k-monopoly number and it is denoted by [M.sub.k] (G). A monopoly of cardinality [M.sub.k] (G) is called a [M.sub.k] (G) -set. In particular notice that for a graph with a leaf (vertex of degree one), there exist only 0-monopolies and the neighbor of every leaf is in each [M.sub.0]-set.

Notice that every non trivial graph G contains at least one k-monopoly, with k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], since every vertex of G satisfies the k-monopoly condition for the whole vertex set V(G). Also, if G has an isolated vertex, [M.sub.k] (G) does not exists. But if G has no isolated vertices, then, since [M.sub.k](G)-set is also a total dominating set, we have [M.sub.k](G) [greater than or equal to] 2. Thus, we can say that in general for any graph G of order n, 2 [less than or equal to] [M.sub.k] (G) [less than or equal to] n. The last result of this section reveals a connection between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (G) and [gamma]t(G).

Theorem 5. For any r-regular graph G,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let M be a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (G)-set. If r is even, then q = 1 and if r is odd, then q = 1/2. In both cases, for any vertex v of G, [[delta].sub.M](v) [greater than or equal to] 1, since [[delta].sub.M](v) is an integer. Hence M is a total dominating set and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If A is a [gamma]t(G)-set, then for every vertex v [member of] V we obtain [[DELTA].sub.A](V) [greater than or equal to] 1 [greater than or equal to] q, since q [member of] {1/2,1}. Thus, A is also a ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII])-monopoly and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which yields the equality. []

3 Complexity

Studies about complexity of signed domination were first presented by Hattingh et al. (1995). After that Henning (2004) has shown that signed total domination problem is NP-complete even restricted to bipartite or chordal graphs. This last work was continued by Liang (2014), where the NP-completeness of signed (total) k-domination problem was shown for k [greater than or equal to] 2. Consequently, by Theorem 1 the k-monopoly problem is also NP-complete for every k [greater than or equal to] 1. Hence, it remains to investigate the complexity of k-monopolies for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As mentioned in the introduction, the complexity and also several inapproximation results are known for a closed monopolies, see Mishra (2012); Mishra and Rao (2006); Mishra et al. (2002); Peleg (2002).

On the other hand, also the global defensive k-alliance problem is NP-complete (unpublished manuscript Fernau (2013)) as well as global offensive k-alliance problem (see Fernau et al. (2009)), but not both together. Notice that global powerful k-alliance problem is NP-complete as shown by Fernau et al. (to appear) but, as we mention before, a global powerful k-alliance is a global defensive k-alliance and a global offensive (k + 2)-alliance. Here we follow a similar approach as Hattingh et al. (1995) to show that 0-monopoly problem is NP-complete. We will show the polynomial time reduction on the total domination set problem:

Problem: TOTAL DOMINATION SET (TDS)

INSTANCE: A graph G and a positive integer k [less than or equal to] | V(G) |.

QUESTION: Is [gamma]t(G) [less than or equal to] k?

Problem: 0-MONOPOLY

INSTANCE: A graph G and a positive integer k [less than or equal to] | V(G) |.

QUESTION: Is [M.sub.0](G) [less than or equal to] k?

Recall that the total domination set problem is NP-complete even when restricted to bipartite graphs (see Laskar and Pfaff (1984)) or to chordal graphs (see Pfaff (1984)).

Theorem 6. Problem 0-MONOPOLY is NP-complete, even when restricted to bipartite or chordal graphs.

Proof: It is obvious that 0-monopoly is a member of NP since for a given set M with |M| [less than or equal to] k we can check in polynomial time for each vertex v of a graph G if v is controlled by M.

Let G be a graph of order n and size m. We construct a graph H from G as follows. For every vertex v add [[delta].sub.G] (v) - 1 paths on five vertices and connect v with an edge to every middle vertex of these paths. Hence to obtain H from G we added 5 [[summation].sub.v[member of]V(G)] ([[delta].sub.G](v) - 1) = 10m - 5n vertices and the same amount of edges. (Notice that we have added exactly 4m - 2n leaves.) Clearly this can be done in polynomial time. Also, if G is bipartite or chordal graph, so is H. Next we claim [M.sub.0] (H) = 6m - 3n + [gamma]t(G).

To prove this, let M be a 0-monopoly of H. Let [v.sub.1][v.sub.2][v.sub.3][v.sub.4][v.sub.5] be an arbitrary path added to G. Clearly [v.sub.2], [v.sub.4] [member of] M, since they are unique neighbors of [v.sub.1] and [v.sub.5], respectively. Moreover, if [v.sub.3] is not in M, then both [v.sub.1] and [v.sub.5] must be in M to control [v.sub.2] and [v.sub.4], respectively. Since M has minimum cardinality, this implies that [v.sub.3] [member of] M. Let v [member of] V(G). By the above, v has [[DELTA].sub.G](v) - 1 neighbors in M outside of G. Since [[delta].sub.H] (v) = 2[[DELTA].sub.G] (v) - 1, v needs an additional neighbor in M [intersection] V(G) = P to be controlled by M. Hence, P forms a total dominating set of G and so [gamma]t(G) [less than or equal to] |P |. Altogether

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

On the other hand, suppose S is a [delta]t(G)-set of G. We will show that M = S [union] {v [member of] V(H) - V(G) : [[DELTA].sub.H] (v) > 1} is a 0-monopoly for H. Every vertex v [member of] V(H) with [[DELTA].sub.H](v) = 1 has a neighbor of degree two which is in M. Without loss of generality, every vertex v [member of] V(H) - V(G) with [[delta].sub.H](v) = 2 has one neighbor of degree 1 and the other neighbor which is in M and we have 1 = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Every other vertex v [member of] V(H) - V(G) has degree three, and two of its neighbors are in V(H) - V(G) with degree two and thus they are in M. Hence 2 = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It remains to check vertices from V(G). Let v be a vertex with de[g.sub.H]H(v) = 2de[g.sub.G] (v) - 1. Since S is a [gamma]t(G) set, v has at least one neighbor in S and additional [[delta].sub.G](v) - 1 vertices in M in V(H) - V(G). Altogether v has at least [[delta].sub.G](v) neighbors in M, which is more than half of its neighbors. The next calculation ends the proof of the claim:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Therefore, we have that if j = 6m - 3n + k, then [gamma]t(G) [less than or equal to] k if and only if [M.sub.0](H) [less than or equal to] j and the proof is completed. ?

Once having studied the complexity of finding a 0-monopoly in a graph, it remains to investigate the complexity for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which we leave as an open problem.

4 Bounding [M.sub.k](G)

In this section we present bounds for [M.sub.k](G) with respect to the minimum and maximum degrees of G and with respect to the order and size. First notice that the k-monopoly condition [[delta].sub.M](v) [greater than or equal to] [delta](v)/2 + k is equivalent to the following expressions:

[[delta].sub.M](v) [greater than or equal to] [delta](v)/2. - k. (3)

Theorem 7. Let G be a graph of order n, minimum degree [delta] and maximum degree [DELTA]. Then for any integerk[member of][MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let A be a set of vertices of G such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let v be a vertex of G. Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which leads to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore [A] is a k-monopoly in G and the upper bound follows.

On the other hand, let M be a [M.sub.k](G)-set and let u be a vertex of maximum degree in G. By (3) we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which leads to [delta]/2 + k [less than or equal to] [[delta].sub.M](u). Now, if u [member of] M, then we obtain that [DELTA]/2 + k [less than or equal to] [[delta].sub.M](u) [less than or equal to] |M| - l and, as a consequence, [DELTA]+2k+2/2 [less than or equal to] |M|. Conversely, if u [??] M, then [DELTA]/2 + k [less than or equal to] [[DELTA].sub.M](u) [less than or equal to] |M| which leads to [DELTA]+2k/2 [less than or equal to]|M|. Therefore, |M| [greater than or equal to] max [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the lower bound follows. []

As the following corollary shows the above bounds are tight.

Corollary 8. For every complete graph [K.sub.n] and every k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: From Theorem 7 we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If n - 2k - 1 is even, then n + 2k + 1 is even and we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, if n - 2k - 1 is odd, then n + 2k + 1 is odd and we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Next we obtain a lower bound for [M.sub.k] (G) in terms of order and size of G.

Theorem 9. For any graph G of order n and size m and for every k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] .

Proof: Let M be a [M.sub.k](G)-set. Since every vertex v [member of] [??] satisfies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c(M, [??]) is the edge cut set between M and [??]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds for every vertex v [member of] M, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which leads to |E([??])| [greater than or equal to] kn. Since m [greater than or equal to] \E([??]) | + c(M, [??]), we obtain that m [greater than or equal to] kn + 2k(n - \M\) = 3kn - 2k|M| and the result follows. []

To see the tightness of the above bound we consider the following family F of graphs. We begin with a complete graph [K.sub.t] with set of vertices V = {[v.sub.0], [v.sub.1],..., [v.sub.t-1]} and t - 1 = 0 (mod 4) and t isolated vertices U = {[u.sub.0]0, [u.sub.1],..., [u.sub.t-1]}. From now on all the operations with subindexes of [u.sub.i] or [u.sub.i] are done modulo t. To obtain a graph G [member of] F, for every i [member of] {0,...,t - 1}, we add the edges [u.sub.i][u.sub.i], [u.sub.i][u.sub.i+1], [u.sub.i][u.sub.i]+2, [u.sub.i][u.sub.i]+(t-3)/2- Notice that G has order 2t and size t(t - 1) and every vertex [u.sub.i] [member of] V has t-1/2 neighbors in U and vice versa. Hence [delta](G) = t-1/2. Suppose k = . If v [member of] V, then [[delta].sub.V](v) = t - 1 = t-1/2+t-1/2=[[delta].sub.U](v) + 2k. Also if v [member of] U,then [[delta].sub.V](v) = t-1/2 = [[delta].sub.U](v)+2k. Thus V is a k-monopoly in G. By Theorem 9 we have [M.sub.k] (G) = t and the bound is achieved.

Theorem 10. For any r-regular graph G of order n and for every k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let V be the vertex set of G and let M be a [M.sub.k](G)-set. For any vertex v [member of] V and any M [subset] V we have that [delta](v) = [[delta].sub.M](v) + [[delta].sub.[??]])(v). By subtracting 2[[delta].sub.[??]](v) in both sides of the equality we obtain [delta](v) - 2[[delta].sub.[??]](V) = [[delta].sub.M](v) - [[delta].sub.[??]](v). Making a sum for every vertex of G and using the fact that G is r-regular, it follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since every vertex v [member of] V satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the result follows.*

As we will see in Proposition 15, the above bound is tight. For instance, it is achieved for the case of cycles [C.sub.4t] for k = 0.

5 Exact values for [M.sub.k](G)

As already mentioned, for any graph G of order n, 2 [less than or equal to] [M.sub.k] (G) [less than or equal to] n. We first characterize the classes of graphs achieving the limit cases for these bounds.

Proposition 11. Let G be a graph of order n. Then [M.sub.k] (G) = 2 if and only if G is isomorphic to [P.sub.2], [P.sub.3], [P.sub.4], [C.sub.3] or [C.sub.4]. Moreover, k is either 0 or 1.

Proof: If G is isomorphic to [P.sub.2], [P.sub.3], [P.sub.4], [C.sub.3] or [C.sub.4], then [delta](G) [less than or equal to] 2, k [member of] {0,1} and [M.sub.k](G) = 2. On the contrary, suppose that [M.sub.k](G) = 2. Let S = {u, v} be a [M.sub.k](G)-set. Notice that u and v must be adjacent. So, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and G must contain at most four vertices. Moreover, for every vertex x [??] (u, v) it follows [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, [delta](G) [less than or equal to]2,k[member of] {0,1} and we have the following cases. If [[delta].sub.[??]](u) = 0 and [[delta].sub.[??]](v) = 0, then G is isomorphic to [P.sub.2]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or vice versa), then G is isomorphic to [P.sub.3]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then G is isomorphic either to [P.sub.4], [C.sub.3] or [C.sub.4], which completes the proof.*

Proposition 12. Let G be a graph of order n and minimum degree [delta]. Then [M.sub.k](G) = n if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and either

(i) [delta] is even and every vertex of G is adjacent to a vertex of degree [delta] or [delta] + 1, or

(ii) [delta] is odd and every vertex of G is adjacent to a vertex of degree [delta].

Proof: Suppose [M.sub.k] (G) = n. Hence, for any vertex v [member of] V (G), M = V (G) - {v} is not k-monopoly in G. Thus the vertex v or some vertex u [member of] N (v) does not satisfy the monopoly condition. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we have that [delta](v) <2k [less than or equal to] [delta], a contradiction. Thus [[delta].sub.M](U) < [[delta].sub.[??]](u) + 2k, which leads to [delta](u) - 1 < 1 + 2k. So [delta](u) [less than or equal to] 2k + 1. As a consequence, we obtain that k [greater than or equal to] [delta]-1/2 (or equivalently [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, if [delta] is even, then we have that [delta](u) [less than or equal to] [delta] +1,andif [delta] is odd, then we have that [delta](u) [less than or equal to] [delta]. Therefore, (i) and (ii) follow.

On the other hand, suppose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume [delta] is even and every vertex of G is adjacent to a vertex of degree [delta] or [delta] +1. Hence, let M [subset] V(G), let x [??] M and let u [member of] N (x) having degree [delta] or [delta] +1. So we have,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, M is not a k-monopoly.

Now, suppose [delta] is odd and every vertex of G is adjacent to a vertex of degree [delta]. As above let M' [subset] V(G), let x' [??] M' and let u' [member of] N(x') having degree [delta]. So we have,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, M' is not a k-monopoly.

Therefore, any proper subset of V(G) is not a k-monopoly and we have that [M.sub.k] (G) = n. []

The wheel graph of order n is defined as [W.sub.1,n] = [K.sub.1] + [C.sub.n-1], where + represents the join of mentioned graphs. The fan graph [F.sub.1,n-1] of order n is defined as the graph [K.sub.1] + [P.sub.n-1].

Corollary 13.

(i) For any r-regular graph G of order n,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (G) = n.

(ii) For any wheel graph [W.sub.1,n-1], [M.sub.1]([W.sub.1,n-1]) = n.

(iii) For any fan graph [F.sub.1,n-1], [M.sub.1]([F.sub.1,n-1]) = n.

(iv) For any bipartite graph [K.sub.r,r+1], r, even, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We continue this section by obtaining exact values for some graph classes. Recall that, by Corollary 8, for k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We continue with complete bipartite graphs.

Proposition 14. For every complete bipartite graph [K.sub.r,t] and every k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let X and Y be the partition sets of [K.sub.r,t] such that |X | = r and |Y | = t and let S be a subset of vertices of [K.sub.r,t] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let v be a vertex of [K.sub.r,t]. If v [member of] X, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Analogously, if v [member of] Y, then we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, S is a k-monopoly in [K.sub.r,t] and we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, let M be a [M.sub.k]([K.sub.r,t])-set and let u be a vertex of [K.sub.r,t]. If u [member of] X, then we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which leads to [[delta].sub.M](u) [greater than or equal to] t+2k/2 and, as a consequence, |Y [intersection] M| = [[delta].sub.M](u) [greater than or equal to] [??]. Analogously, if u [member of] Y, then we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the proof is complete. []

Next we study k-monopolies of cycles and paths. First notice that the case k = 1 for cycles follows directly from Corollary 13 (i), that is, [M.sub.1]([C.sub.n]) = n.

Proposition 15. For every integer n [greater than or equal to] 3,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By Theorem 5, [M.sub.0]([C.sub.n]) = [gamma]t([C.sub.n]) and it is known from Henning (2000) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we are done with cycles.

Let V([P.sub.n]) = {[v.sub.0],..., [v.sub.n-1]}. We proceed by induction on k [greater than or equal to] 1 where n = 4k + i and i [member of] {-1,0,1,2}. Let [M.sub.n] be a subset of V([P.sub.n]) defined as follows.

* If n = 0 (mod 4), then [M.sub.n] = {[v.sub.1], [v.sub.2], [v.sub.5], [v.sub.6],... [v.sub.n-3], [v.sub.n-2]}.

* If n = 1 (mod 4), then [M.sub.n] = {[v.sub.1], [v.sub.2], [v.sub.3], [v.sub.6], [v.sub.7], [v.sub.10], [v.sub.11],..., [v.sub.n-3], [v.sub.n-2]}.

* If n = 2 (mod 4), then [M.sub.n] = {[v.sub.0], [v.sub.1], [v.sub.3], [v.sub.4], [v.sub.7], [v.sub.8], [v.sub.11], [v.sub.12],..., [v.sub.n-3], [v.sub.n-2]}.

* If n = 3 (mod 4), then [M.sub.2] = {[v.sub.0], [v.sub.1], [v.sub.4], [v.sub.5],..., [v.sub.n-3], [v.sub.n-2]}.

It is straightforward to check that [M.sub.n] is a [M.sub.0]([P.sub.n])-set for k = 1. Notice that [M.sub.4] is the unique [M.sub.0]([P.sub.4])-set. Let k > 1. Set [M.sub.4(k-1)+i] is a [M.sub.0]([P.sub.4(k-1)+i]) -set by induction hypothesis. Clearly, any 0-monopoly M' of [P.sub.n] contains at least two vertices of the last three vertices [v.sub.n-3],[v.sub.n-2], [v.sub.n-1]. Hence, these two vertices have no influence on the vertices of M' from the first 4(k - 1) + i vertices of the path [P.sub.4k+i]. Therefore |M' [intersection] {[v.sub.0],...,[v.sub.4(k-1)+i]}| [greater than or equal to] |[M.sub.4(k-1)+i]| and [M.sub.4k+i] = [M.sub.4(k-1)+i] [union] {[v.sub.n-3], [v.sub.n-2]} is a [M.sub.0]([P.sub.4k+i])-Set. It is easy to see that |[M.sub.4k+i] | gives the desired values. []

6 Partitions into k-monopolies

In this section we present some results about partitioning a graphs into monopolies. To this end, we say that a graph G = (V, E) is k-monopoly partitionable if there exists a vertex partition II = {[S.sub.1];...,[S.sub.r]} of V, r [greater than or equal to] 2, such that for every i [member of] {1,..., r}, [S.sub.i] is a k-monopoly in G.

Theorem 16. If a graph G is k-monopoly partitionable, for some k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then r [less than or equal to] 2 - 2k and k [less than or equal to] 0.

Proof: Let [S.sub.i], [S.sub.j] [member of] II and let v be a vertex of G. Then we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since for every u of G, [??] (u) [greater than or equal to] 1 for every [??] [member of] {1,...,r}, we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus 2k + r - 2 [less than or equal to] 0, which leads to r [less than or equal to] 2 - 2k and k [less than or equal to] 1 - r/2. Since r [greater than or equal to] 2, we have that k [less than or equal to] 0. []

From the above result we have that G can be only partitioned into at most 2 - 2k k-monopolies for k [less than or equal to] 0. The particular case k = 0 is next studied. Notice that for instance, cycles of order 4t and hypercubes [Q.sub.2t] with t [greater than or equal to] 1 are examples of graphs having a partition into two 0-monopolies.

Proposition 17. Let G be a graph having a vertex partition into two 0-monopolies {X, Y}. Then the following assertions are satisfied.

(i) For every vertex v of G, [[delta].sub.X] (v) = [[delta].sub.Y](v).

(ii) For every vertex v of G, [delta](v) is an even number.

(iii) The size [m.sub.x] of [??] equals the size [m.sub.y] of [??].

(iv) The cardinality of the edge cut set c(X, Y) produced by the vertex partition {X, Y} equals the size m ofG minus two times the size of [??].

Proof: For every vertex v of G we have that [[delta].sub.X] (v) [greater than or equal to] [[delta].sub.Y] (v) and [[delta].sub.Y] (v) [greater than or equal to] [[delta].sub.x] (v). Thus, (i) follows. Now, (ii) follows from the fact that [delta](v) = [[delta].sub.X] (v) + [[delta].sub.Y] (v) = 2[[delta].sub.X] (v) = 2[[delta].sub.Y] (v). To prove (iii) we consider the following

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since, [[summation].sub.v[member of]Y] [[delta].sub.X] (v) = [[summation].sub.v[member of]Y] [[delta].sub.Y](v) we have the result. As a consequence, m = c(X, Y) +[m.sub.x] + [m.sub.Y] and by (iii) we obtain (iv). []

A natural question which now arises concerning the computational complexity on the existence of such partitions mentioned above. That is for instance, given a graph G, can we decide whether G is k-monopoly partitionable? Moreover, if the answer is positive, can we find such partitions by using some efficient algorithm?

References

J.-C. Bermond, J. Bond, D. Peleg, and S. Perennes. The power of small coalitions in graphs. Discrete Applied Mathematics, 127(3):399-414, 2003. doi: 10.1016/S0166-218X(02)00241-X. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-84867959143&partnerID=40&md5=df993bddbdf24f26b0f2554323bce429.

J. Dunbar, S. Hedetniemi, M. Henning, and P. Slater. Signed domination in graphs. Graph Theory, Combinatorics, and Applications, pages 311-322, 1995.

C. Dwork, D. Peleg, N. Pippenger, and E. Upfal. Fault tolerance in networks of bounded degree. SIAM Journal on Computing, 17(5):975-988, 1988. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-0024 09129 9&partnerID=40&md5=009c11dd0d050861b69499d3fbf93566.

O. Favaron, G. Fricke, W. Goddard, S. Hedetniemi, S. Hedetniemi, P. Kristiansen, R. C. Laskar, and R. Skaggs. Offensive alliances in graphs. Discussiones Mathematicae Graph Theory, 24:263-275, 2004.

H. Fernau. Private communication. 2013.

H. Fernau and J. Rodriguez-Velazquez. A survey on alliances and related parameters in graphs. Electronic Journal of Graph Theoryand Applications, 2(1):70-86, 2014.

H. Fernau, J. Rodriguez-Velazquez, and J. Sigarreta. Offensive r-alliances in graphs. Discrete Applied Mathematics, 157(1): 177-182, 2009. doi: 10.1016/j.dam.2008.06.001. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-5664 9115970&partnerID=40&md5=ec6162e86b28fe3af48f2f1c64169a75.

H. Fernau, J. Rodriguez-Velazquez, and J. Sigarreta. Global powerful r-alliances and total k-domination in graphs. Utilitas Mathematica, to appear.

P. Flocchini, R. Kralovic, P. Ruzicka, A. Roncato, and N. Santoro. On time versus size for monotone dynamic monopolies in regular topologies. Journal of Discrete Algorithms, 1(2): 129-150, 2003. doi: 10.1016/S1570-8667(03)00022-4. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-77952569578&partnerID=4 0&md5=bc3c283a056a43366c34cdffad9c85e3.

H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. Journal of the ACM, 32(4):841-860, 1985. doi: 10.1145/4221.4223. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-0022145769&partnerID=40&md5=19a2ca07b3b1f38508e2926817239acd.

J. Hattingh, M. Henning, and P. Slater. The algorithmic complexity of signed domination in graphs. Australasian Journal ofCombinatorics, 12:101-112, 1995.

T. Haynes, S. Hedetniemi, and M. Henning. Global defensive alliances in graphs. Electronic Journal of Combinatorics, 10(1 R), 2003. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-3042 619803&partnerID=40&md5=de525879814c4abbf82b4b7d27f52fa4.

M. Henning. Graphs with large total domination number. Journal of Graph Theory, 35 (1):21-45, 2000. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-23044518657&partnerID=40&md5=eda9769f06132678c59dd3470b350fe7.

M. Henning. Signed total domination in graphs. Discrete Mathematics, 278(1-3):109-125, 2004. doi: 10.1016/j.disc.2003.06.002. URL http://www.scopus.com/inward/record.url?eid= 2-s2.0-1142263889&partnerID=40&md5=20dd482bbe17d6173990b948169f1bbe.

K. Khoshkhah, M. Nemati, H. Soltani, and M. Zaker. A study of monopolies in graphs. Graphs and Combinatorics, 29(5):1417-1427, 2013. doi: 10.1007/s00373-012-1214-7. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-84882903032&partnerID=40&md5=9962cc0de8828815ac6749b93652024d.

P. Kristiansen, S. Hedetniemi, and S. Hedetniemi. Alliances ingraphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 48:157-177, 2004.

R. Laskar and J. Pfaff. Domination and irredundance in split graphs. Technical Report, Department of Mathematical Sciences, Clemson University, 10(1):49-60, 1984. doi: 10.1016/j.jda.2011.12.019. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-84855548350&partnerID=40&md5=468858cae7328c688f73b0e203b00ac6.

H. Liang. On the signed (total) k-domination number of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 89:87-99, 2014.

N. Linial, D. Peleg, Y. Rabinovich, and M. Saks. Sphere packing and local majorities in graphs. 2nd Israel Symposium on Theory and Computing Systems, pages 141-149, 1993.

S. Mishra. Complexity of majority monopoly and signed domination problems. Journal of Discrete Algorithms, 10(1):49-60, 2012. doi: 10.1016/j.jda.2011.12.019. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-848 55548350&partnerID=40&md5=468858cae7328c688f73b0e203b00ac6.

S. Mishra and S. Rao. Minimum monopoly in regular and tree graphs. Discrete Mathematics, 306(14):1586-1594, 2006. doi: 10.1016/j.disc.2005.06.036. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-33745656404&partnerID=40&md5=0f2c2e220120fbe991066315ad65cdc6.

S. Mishra, J. Radhakrishnan, and S. Sivasubramanian. On the hardness of approximating minimum monopoly problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2556 LNCS: 277-288, 2002. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-80052395587&partnerID=40&md5=cb24b2adb61a5dbff36910d9addba94c.

D. Peleg. Local majorities, coalitions and monopolies in graphs: A review. Theoretical Computer Science, 282(2):231-257, 2002. doi: 10.1016/S0304-3975(01)00055-X. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-0037054318&partnerID=40&md5=32b9c2596729f62832b1564d367adccc.

J. Pfaff. Algorithmic complexities of domination-related graph parameters. Ph.D. Thesis, Clemson University, 1984.

K. Shafique and R. Dutton. Maximum alliance-free and minimum alliance-cover sets. Congressus Numerantium, 162:139-146, 2003.

K. Shafique and R. Dutton. A tight bound on the cardinalities of maximun alliance-free and minimun alliance-cover sets. Journal of Combinatorial Mathematics and Combinatorial Computing, 56:139-145, 2006.

G. Sullivan. The complexity of system-level fault diagnosis and diagnosability. Ph. D. Thesis, Yale University New Haven. CT, 1986.

M. Zaker. On dynamic monopolies of graphs with general thresholds. Discrete Mathematics, 312(6):1136-1143, 2012. doi: 10.1016/j.disc.2011.11.038. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-84155191040&partnerID=40&md5=c463fb9151e8e07ebad6dc45643a750e.

B. Zelinka. Signed total domination number of a graph. Czechoslovak Mathematical Journal, 51 (2):225-229, 2001. URL http://www.scopus.com/inward/record.url?eid=2-s2.0-23044528767&partnerID=40&md5=9024d6b751af95d67c4254a2d6a091e6.

Dorota Kuziak (1)

Iztok Peterin (2,3*)

Ismael G. Yero (4)

(1) Departament d'Enginyeria Informatica i Matemaatiques, Universitat Rovira i Virgili, Spain

(2) University of Maribor, Faculty of Electrical Engineering and Computer Science, Slovenia

(3) Institute of Mathematics, Physics and Mechanics, Slovenia

(4) Escuela Politecnica Superior, Universidad de Cadiz, Spain

received 12th June 2015, revised 17th Nov. 2015, accepted 7th Mar. 2016.

(*) Partially supported by the Ministry of Science of Slovenia under the grant P1-0297.

(i) A set D is a total dominating set in a graph G if every vertex of G is adjacent to a vertex of D. The minimum cardinality of a total dominating set is the total domination number, denoted by t(G).

Printer friendly Cite/link Email Feedback | |

Author: | Kuziak, Dorota; Peterin, Iztok; Yero, Ismael G. |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Date: | Nov 1, 2016 |

Words: | 9340 |

Previous Article: | Factoriality and the Pin-Reutenauer procedure. |

Next Article: | Sticky seeding in discrete-time reversible-threshold networks. |

Topics: |