EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 12, No. 3, 2019, 978-998 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Cost Effective Domination in the Join, Corona and Composition of Graphs Ferdinand P. Jamil1, Hearty M. Nuenay- Maglanque2,∗ 1 Department of Mathematics and Statistics, College of Science and Mathematics Center for Graph Theory, Algebra and Analysis, PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Department of Applied Mathematics, College of Science and Mathematics, University of Science and Technology of Southern Philippines, 9000 Cagayan de Oro City, Philippines Abstract. Let G be a connected graph. A cost effective dominating set in a graph G is any set S of vertices of G satisfying the condition that each vertex in S is adjacent to at least as many vertices outside S as inside S and every vertex outside S is adjacent to at least one vertex in S. The minimum cardinality of a cost effective dominating set is the cost effective domination number of G. The maximum cardinality of a cost effective dominating set is the upper cost effective domination number of G. A cost effective dominating set is said to be minimal if it does not contain a proper subset which is itself a cost effective dominating in G. The maximum cardinality of a minimal cost effective dominating set in a graph G is the minimal cost effective domination number of G. In this paper, we characterized the cost effective dominating sets in the join, corona and composition of graphs. As direct consequences, the bounds or the exact cost effective domination numbers, minimal cost effective domination numbers and upper cost effective domination numbers of these graphs were obtained. 2010 Mathematics Subject Classifications: 05C12 Key Words and Phrases: Cost effective dominating set, cost effective domination number, join, corona, composition 1. Introduction Throughout this paper, we consider simple, finite and undirected connected graphs G = (V (G), E(G)). All basic graph theoretic concepts used here are adapted from [1]. The symbols V (G) and E(G) are the vertex set and edge set, respectively, of G. For S ⊆ V (G), |S| is the cardinality of S. In particular, |V (G)| is called the order of G. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v12i3.3443 Email addresses: ferdinand.jamil@g.msuiit.edu.ph (F. Jamil), hearty15200@yahoo.com.ph (H. Nuenay-Maglanque) http://www.ejpam.com 978 c© 2019 EJPAM All rights reserved. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 979 Given graphs G and H with disjoint vertex sets, the join of G and H is the graph G+H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)}. The corona of G and H is the graph G ◦ H obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. The composition (or lexicographic product) G[H] of G and H is the graph with V (G[H]) = V (G)× V (H) and (u, v)(u′, v′) ∈ E(G[H]) if and only if either uu′ ∈ E(G) or u = u′ and vv′ ∈ E(H). For v ∈ V (G), the neighborhood of v is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)}. The degree of a vertex v ∈ V (G), denoted by degG(v), is equal to the cardinality of NG(v) and the maximum degree of G is ∆(G) = max{degG(v) : v ∈ V (G)}. A vertex is isolated if its degree is zero, and a graph is isolate-free if it has no isolated vertices. For S ⊆ V (G), NG(S) = ∪v∈SNG(v) and NG[S] = S ∪ NG(S). A dominating set of G is any S ⊆ V (G) for which NG[S] = V (G). The domination number of G, denoted by, γ(G) is the smallest cardinality of a dominating set of G. A dominating set S of G is said to be a minimal dominating set if it has no proper subset which is itself a dominating set in G. The maximum cardinality of a minimal domination set in G is denoted by γm(G). A dominating set S is said to be an independent dominating set of G if for every two vertices u, v ∈ S, uv /∈ E(G). The minimum cardinality of an independent dominating set is called an independent domination number and is denoted by i(G). We refer to [2–7] for the fundamental concepts and history of the theory of domination in graphs as well as for some of its relevant applications. Investigation of the concept in the join, corona or composition of graphs can be found in [8, 9, 13]. A subset S ⊆ V (G) is said to be a cost effective set of G if for every v ∈ S, |NG(v)∩S| ≤ |NG(v) \ S|. A subset S ⊆ V (G) is said to be a very cost effective set of G if for every v ∈ S, |NG(v) ∩ S| < |NG(v) \ S|. A subset S ⊆ V (G) is said to be a (very)cost effective dominating set of G if S is both a (very) cost effective set and a dominating set of G. The minimum (resp. maximum) cardinality of a cost effective dominating set of a graph G is called the cost effective domination number (resp. upper cost effective domination number) of G, and is denoted by γce(G) (resp. γ+ce(G)). The minimum cardinality of a very cost effective dominating set of a graph G is called the very cost effective domination number of G, and is denoted by γvce(G). An excellent introduction and exposition on cost effective domination in graphs can be found in [11, 12]. A cost effective dominating set S ⊆ V (G) is a minimal cost effective set if S does not contain a proper subset which is itself a cost effective dominating set. We use the symbol γmce(G) to denote the maximum cardinality of a minimal cost effective dominating set of G. It is worth noting that, in particular, an independent dominating set is a minimal cost effective dominating set. Clearly γ(G) ≤ γce(G) ≤ γmce(G) ≤ γ+ce(G) for all graphs G. For simplicity, we use the terms ced-set, γce-set, γ+ce-set and γmce-set to refer to the cost effective dominating set, the cost effective dominating sets with cardinality γce(G), γ+ce(G) and γmce(G), respectively. In this paper we characterized the cost effective dominating sets and minimal cost effective dominating sets in the join, corona and composition of graphs. As consequences, we determined the cost effective domination number, minimal cost effective domination F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 980 number and upper cost effective domination number of the aforementioned graphs. 2. Cost Effective Domination in the Join of Graphs Remark 1. Given two connected graphs G and H, a ced-set S of G+H, where S ⊆ V (G), need not be a ced-set of G as shown in Example 1. Example 1. Let G = K5 ◦K3. Consider the graph G+K1 as shown in Figure 1. v1 v2 v3 v4 v5 u Figure 1: The graph G+K1 Observe that the set {v1, v2, v3, v4, v5} ⊆ V (G) is a cost effective dominating set of G+K1 but not a cost effective dominating set of G. Proposition 1. Let G be a nontrivial connected graph and H be any graph. If S ⊆ V (G) is a cost effective dominating set of G, then S is a very cost effective dominating set of G+H. Proof. Let S ⊆ V (G) be a cost effective dominating set of G. Then S is a dominating set of G+H. For each v ∈ S, |NG+H(v) ∩ S| = |NG(v) ∩ S| ≤ |NG(v) \ S| < |NG(v) \ S|+ |V (H)| = |NG+H(v) \ S|. Thus, S is a very cost effective dominating set of G+H. Theorem 1. Let G and H be nontrivial graphs of orders m and n, respectively, and let S ⊆ V (G+H). Then S is a cost effective dominating set of G+H if and only if one of the following holds: (i) S ⊆ V (G) is a dominating set of G and |NG(v) ∩ S| ≤ n+ |NG(v) \ S| for all v ∈ S (ii) S ⊆ V (H) is a dominating set of H and |NH(v)∩S| ≤ m+ |NH(v)\S| for all v ∈ S (iii) S ∩ V (G) 6= ∅ and S ∩ V (H) 6= ∅ satisfying (a) |NG(v) ∩ S|+ 2|S ∩ V (H)| ≤ n+ |NG(v) \ S| for all v ∈ S ∩ V (G) (b) |NH(v) ∩ S|+ 2|S ∩ V (G)| ≤ m+ |NH(v) \ S| for all v ∈ S ∩ V (H). F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 981 Proof. Let S ⊆ V (G+H). Suppose that S is a cost effective dominating set of G+H. If S ⊆ V (G), then S is a dominating set of G, and for each v ∈ S, |NG(v) ∩ S| = |NG+H(v) ∩ S| ≤ |NG+H(v) \ S| = n+ |NG(v) \ S|. Similarly, if S ⊆ V (H), then S is dominating of H and for each v ∈ S, |NH(v) ∩ S| ≤ m + |NH(v) \ S|. Suppose that S1 = S ∩ V (G) 6= ∅ and S2 = S ∩ V (H) 6= ∅. For each v ∈ S1, |NG(v) ∩ S|+ |S2| = |NG+H(v) ∩ S| ≤ |NG+H(v) \ S| = |NG(v) \ S|+ |V (H) \ S2| = |NG(v) \ S|+ n− |S2| Thus, |NG(v) ∩ S|+ 2|S2| ≤ n+ |NG(v) \ S|. Similarly, for each v ∈ S2, |NH(v) ∩ S|+ 2|S1| ≤ m+ |NH(v) \ S|. Conversely, suppose that S satisfies Property (i). Then S is a dominating set of G + H. Let v ∈ S. Then |NG+H(v) ∩ S| = |NG(v) ∩ S| ≤ n+ |NG(v) \ S| = |NG+H(v) \ S|. Thus, S is a cost effective set of G+H, and the conclusion follows. Similarly, if S satisfies (ii), then S is a cost effective dominating set of G+H. Finally, suppose that S satisfies (iii). Then S is a dominating set of G+H. For each v ∈ S ∩ V (G), we have from Property (iii)(a), |NG+H(v) ∩ S| = |NG(v) ∩ S|+ |NH(v) ∩ S| = |NG(v) ∩ S|+ |S ∩ V (H)| ≤ n+ |NG(v) \ S| − 2|S ∩ V (H)|+ |S ∩ V (H)| = n+ |NG(v) \ S| − |S ∩ V (H)| = |NG(v) \ S|+ |V (H) \ S| = |NG+H(v) \ S|. Similarly, for each v ∈ S∩V (H), |NH(v)∩S|+ 2|S∩V (G)| ≤ m+ |NH(v)\S|. Therefore, S is a cost effective dominating set of G+H. In view of Theorem 1, all independent dominating sets of G and all independent dominating sets of H are cost effective dominating sets of G + H. Moreover, if m and n are the orders of G and H, respectively, and if m ≤ n, then all dominating sets of G are cost effective dominating sets of G+H so that γce(G+H) ≤ γ(G). F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 982 Corollary 1. For any graphs G and H, γce(G+H) =  1, if γ(G) = 1 or γ(H) = 1 2, otherwise. Proof. Suppose that γ(G) = 1, and let S = {v} be a γ-set of G. Then, |NG+H(v)∩S| = |NG(v) ∩ S| = 0 < |NG+H(v) \ S|. Thus, S is a cost effective dominating set of G + H, showing that γve(G + H) = 1. Similarly, if γ(H) = 1, then γce(G + H) = 1 . Suppose that γ(G) ≥ 2 and γ(H) ≥ 2. Let S = {u, v}, where u ∈ V (G) and v ∈ V (H). Then S satisfies Theorem 1(iii) so that S is a cost effective dominating set of G+H. In this case, γce(G+H) = 2. Theorem 2. Let G and H be nontrivial graphs of orders m and n, respectively, and let S ⊆ V (G + H). Then S is a minimal cost effective dominating set of G + H if and only if one of the following holds: (i) S ⊆ V (G) is a minimal dominating set of G and |NG(v) ∩ S| ≤ n+ |NG(v) \ S| for all v ∈ S (ii) S ⊆ V (H) is a minimal dominating set of H and |NH(v)∩S| ≤ m+ |NH(v) \S| for all v ∈ S (iii) S = {u, v}, where u ∈ V (G) and v ∈ V (H) do not dominate V (G) and V (H), respectively. Proof. Suppose that S is a minimal cost effective dominating set of G + H. Suppose that S ⊆ V (G). By Theorem 1, S is a dominating set of G satisfying |NG(v) ∩ S| ≤ n+ |NG(v) \ S| (1) for all v ∈ S. Suppose that S is not a minimal dominating set of G. Then, there exists a dominating set S∗ ⊆ S of G with |S∗| ≤ |S|. Since |NG+H(v) ∩ S∗| = |NG(v) ∩ S∗| ≤ NG(v) ∩ S| = |NG+H(v) \ S| ≤ |NG+H(v) \ S∗| for all v ∈ S∗, S∗ is a cost effective dominating set of G, contrary to the minimality of S. Thus, S is a minimal dominating set of G. Similarly, if S ⊆ V (H), then Property (ii) holds. Suppose that S ∩ V (G) 6= ∅ and S ∩ V (H) 6= ∅. Pick any u ∈ S ∩ V (G) and v ∈ S ∩ V (H). Then {u, v} satisfies Theorem 1(iii), and is thus a cost effective dominating set of G + H. Therefore, in this case, if S is a minimal cost effective set of G+H, then S = {u, v} for some u ∈ V (G) and v ∈ V (H). Moreover, u and v do not dominate V (G) and V (H), respectively. Conversely, following similar arguments, if Property (i) or Property (ii) holds, then S is a minimal cost effective dominating set of G + H. Suppose that S = {u, v}, where u ∈ V (G) and v ∈ V (H) and u and v do not dominate V (G) and V (H), respectively. By Theorem 1, S is a cost effective dominating set of G + H. Since u and v each does not dominate V (G+H), S is a minimal cost effective dominating set of G+H. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 983 Corollary 2. Let G and H be isolate-free graphs with G noncomplete. Then, max{γmce(G), γmce(H)} ≤ γmce(G+H) ≤ max{γm(G), γm(H)}. Proof. Let S ⊆ V (G + H) be a γmce-set of G + H. In view of Theorem 2, since G is noncomplete, γmce(G+H) ≥ 2. By the same theorem, if S ⊆ V (G), then S is a minimal dominating set of G so that |S| ≤ γm(G). Similarly, if S ⊆ V (H), then |S| ≤ γm(H). Hence, γmce(G+H) ≤ max{γm(G), γm(H)}. On the other hand, by Proposition 1 and Theorem 1, every minimal cost effective dominating set of G is a minimal cost effective dominating set of G+H. Thus, γmce(G) ≤ γmce(G + H). Similarly, γmce(H) ≤ γmce(G + H). Thus, max{γmce(G), γmce(H)} ≤ γmce(G+H). Therefore, max{γmce(G), γmce(H)} ≤ γmce(G+H) ≤ max{γm(G), γm(H)}. Corollary 3. Let G be any isolate-free graph and m ≥ 1. Then γmce(G) ≤ γmce(G+Km) ≤ γm(G). In particular, if G is any of the following: Kn,Kr,s, Pn, Cn, then γmce(G+Km) = γmce(G). In view of Corollary 3 and results on the minimal dominating sets by [10], the lower and upper bounds in Corollary 2 are sharp. The following is directly from Proposition 1. Proposition 2. For any connected graph G, γ+ce(G) ≤ γ+ce(G+K1), and this bound is sharp. Consider the graph G = Kn for n = 2k + 1, k ≥ 0. Note that γ+ce(Kn) = ⌊ n+ 1 2 ⌋ = ⌊ 2k + 1 + 1 2 ⌋ = k + 1. Now, G+K1 = Kn+1 where n+ 1 is even. Now, γ+ce(G+K1) = γ+ce(Kn+1) = ⌊ (2k + 1 + 1) + 1 2 ⌋ = ⌊ 2k + 3 2 ⌋ = k + 1 = γ+ce(G). Thus, the bound in Proposition 2 is sharp. However, strict inequality in Proposition 2 may be attained as illustrated by the fol- lowing example. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 984 v2 v4 v3 v1 v5 v6 u Figure 2: G+K1 Example 2. Let G = C3 ◦K1 and V (G) = {v1, v2, . . . , v6}. Consider the join G+K1 as shown in Figure 2. Observe that the set {v2, v5, v6} is a γ+ce-set of G. On the other hand, the set {v2, v5, v6, u} is a γ+ce-set in G+K1. Thus, γ+ce(G) = 3 < 4 = γ+ce(G+K1). . Remark 2. [11] For any connected graph G of order n ≥ 2, γce(G) ≤ ⌊ n 2 ⌋ . Theorem 3. Let G and H be any connected nontrivial graphs. Then, max { γ+ce(G), γ+ce(H), α+ β } ≤ γ+ce(G+H), where α = max { |S| : S ⊆ V (G) is a ced-set of G with |S| ≤ ⌊m 2 ⌋} , and β = max { |S| : S ⊆ V (H) is a ced-set of H with |S| ≤ ⌊n 2 ⌋} . Proof. First, note that the existence of α and β is guaranteed by Remark 2. By Proposition 1 and Theorem 1, every γ+ce-set of G is a cost effective dominating set of G+H. Hence, γ+ce(G+H) ≥ γ+ce(G). Similarly, γ+ce(G+H) ≥ γ+ce(H). Now, let S1 ⊆ V (G) be a cost effective dominating set of G with |S1| ≤ ⌊ m 2 ⌋ , and S2 ⊆ V (H) a cost effective dominating set of H with |S2| ≤ ⌊ n 2 ⌋ , and put S = S1∪S2. For each v ∈ S1, |NG(v) ∩ S|+ 2|S2| ≤ |NG(v) \ S|+ 2 ⌊n 2 ⌋ ≤ |NG(v) \ S|+ n. Similarly, for each v ∈ S2, |NG(v) ∩ S|+ 2|S1| ≤ |NG(v) \ S|+m. By Theorem 1, S is a cost effective dominating set of G + H. Thus, |S| ≤ γ+ce(G + H). Since S1 and S2 are arbitrary, α + β ≤ γ+ce(G + H). The inequality follows immediately. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 985 Theorem 4. Let G be a connected graph of order m. Then for n ≥ m, γ+ce(G+Kn) ≤ m+ n+ 1 2 . Proof. Let S ⊆ V (G + Kn) be a γ+ce-set of G + Kn. Since S is a γ+ce-set and V (G) satisfies Theorem 1(i), if S ⊆ V (G), then S = V (G). Suppose that S ⊆ V (Kn). Then S is dominating set of Kn and for a given v ∈ S, |S| − 1 = |NKn(v) ∩ S| ≤ m + |NKn(v) \ S| = m + n − |S| so that |S| ≤ m+n+1 2 . Now suppose that S1 = S ∩ V (G) 6= ∅ and S2 = S ∩ V (Kn) 6= ∅. By Theorem 1, in particular, for each u ∈ S2, 2|S1| ≤ m+ |NKn(u) \ S| − |NKn(u) ∩ S| = m+ n− 2|S2|+ 1, or equivalently, |S| ≤ m+ n+ 1 2 . 3. Cost Effective Domination in the Corona of Graphs Theorem 5. [8] Let G be a connected graph of order n and let H be any graph of order m. Then S ⊆ V (G ◦H) is a dominating set of G ◦H if and only if S ∩ V (Hv + v) is a dominating set of Hv + v for each v ∈ V (G). Corollary 4. Let G be a connected graph and H be any graph, and S ⊆ V (G ◦ H). If S is a cost effective dominating set of G ◦H, then S ∩ V (Hv + v) is a dominating set of Hv + v for each v ∈ V (G). Corollary 4 guarantees that if S is a cost effective dominating set of G ◦ H, then S ∩ V (Hv + v) 6= ∅ for each v ∈ V (G). Proposition 3. Let G be a connected graph and H be any isolate-free graph. If for each v ∈ V (G), Sv ⊆ V (Hv) is a cost effective dominating set of Hv, then ∪v∈V (G)Sv is a cost effective dominating set of G ◦H. Proof. For each v ∈ V (G), let Sv ⊆ V (Hv) be a cost effective dominating set of Hv. Then Sv is a very cost effective dominating set of Hv + v, by Proposition 1. Let S = ∪v∈V (G)Sv. Then S is a dominating set of G ◦H. Let u ∈ Sv. Then, |NG◦H(u) ∩ S| = |NHv+v(u) ∩ Sv| ≤ |NHv+v(u) \ Sv| = |NG◦H(u) \ S|, showing that S is a cost effective dominating set of G ◦H. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 986 Proposition 4. Let G be a connected graph and H be any graph of order n ≥ 2. For each v ∈ V (G) with degG(v) ≤ n, let Sv = {v}, and for each v ∈ V (G) with degG(v) > n, let Sv ⊆ V (Hv) be a cost effective dominating set of Hv. Then ∪v∈V (G)Sv is a cost effective dominating set of G ◦H. Consequently, γce(G ◦H) ≤ |V (G)|+ (γce(H)− 1)|L|, where L = {v ∈ V (G) : degG(v) > n}. Proof. Let S = ∪v∈V (G)Sv. Then S is a dominating set of G ◦ H. Let v ∈ V (G) with degG(v) ≤ n. Then |NG◦H(v) ∩ S| ≤ degG(v) ≤ n ≤ |NG◦H(v) \ S|. Suppose that degG(v) > n. Then Sv is a cost effective dominating set of Hv. By Proposition 1, Sv is a very cost effective dominating set of Hv + v. Thus, for each u ∈ Sv, |NG◦H(u) ∩ S| = |NHv+v(u) ∩ Sv| < |NHv+v(u) \ Sv| = |NG◦H(u) \ S|. Therefore, S is a cost effective dominating set of G ◦H. Corollary 5. For any nontrivial connected graph G of order m and any graph H, if ∆(G) ≤ |V (H)|, then γce(G ◦H) = m. Definition 1. Let G be any graph. A subset S ⊆ V (G) is called a Kn-cost effective set of G if S is a cost effective set of Kn +G. A Kn-cost effective set which is dominating in G is called a Kn-cost effective dominating set of G. A Kn-cost effective dominating set is called minimal Kn-cost effective dominating set if it does not contain a proper subset that is itself Kn-cost effective dominating set. The symbols γKnce(G), γKnmce(G) and γ+Knce (G) denote the minimum cardinality of a Kn-cost effective dominating set, the maximum cardinality of a minimal Kn-cost ef- fective dominating set and maximum cardinality of a Kn-cost effective dominating set, respectively, in G. Remark 3. Every cost effective (dominating) set of G is a Kn-cost effective (dominating) set of G. Consequently, γKnce(G) ≤ γce(G) and γ+ce(G) ≤ γ+Knce (G). Remark 4. If C1, C2, . . . , Cn are the components of a graph G and S ⊆ V (G), then S is a Kn-cost effective dominating set of G if and only if S ∩ V (Ck) is a Kn-cost effective dominating set of Ck for all k = 1, 2, . . . , n. Lemma 1. Let G be a connected graph and H any graph, and let S ⊆ V (G ◦ H) and v ∈ V (G)\S. If S is a cost effective dominating set of G◦H, then S∩V (Hv) is a K1-cost effective dominating set of Hv. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 987 Proof. Suppose that S is a cost effective dominating set of G◦H and v ∈ V (G)\S. Let Sv = S∩V (Hv) and let u ∈ Sv. Then, |NHv+v(u)∩Sv| = |NG◦H(u)∩S| ≤ |NG◦H(u)\S| = |NHv+v(u) \ Sv|. Theorem 6. Let G be a connected graph and H an isolate-free graph of order n, and let S ⊆ V (G ◦H). Then S is a cost effective dominating set of G ◦H if and only if the following hold: (i) For each v ∈ S ∩ V (G), S ∩ V (Hv) is a cost effective set of Hv satisfying |S ∩ V (Hv)| ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|) . (ii) For each v ∈ V (G) \ S, S ∩ V (Hv) is a K1-cost effective dominating set of Hv Proof. Suppose that S is a cost effective dominating set of G ◦ H. By Corollary 4, S ∩ V (Hv + v) is a dominating set of Hv + v for each v ∈ V (G). Let v ∈ S ∩ V (G), and put Sv = S ∩ V (Hv). We claim that Sv is a cost effective set of Hv. Let u ∈ Sv. Then 1 + |NHv(u) ∩ Sv| = |NHv+v(u) ∩ S| = |NG◦H(u) ∩ S| ≤ |NG◦H(u) \ S| = |NHv(u) \ Sv|. Necessarily, |NHv(u) ∩ Sv| < |NHv(u) \ Sv|. Since u is arbitrary, Sv is a cost effective set of Hv. Further, since v ∈ S, |NG(v) ∩ S|+ |Sv| = |NG◦H(v) ∩ S| ≤ |NG◦H(v) \ S| = |NG(v) \ S|+ n− |Sv|, or equivalently, |Sv| ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|) . This establishes Property (i). Property (ii) follows immediately from Lemma 1. Conversely, suppose that S satisfies all the above prescribed properties. In any case, for v ∈ V (G), S ∩ V (Hv + v) is a dominating set of Hv + v. Thus, S is a dominating set of G ◦H by Theorem 5. Let u ∈ S. In view of Corollary 4, u ∈ S ∩ V (Hv + v) for some v ∈ V (G). Suppose that v ∈ S. By Property (i), Sv = S ∩ V (Hv) is a cost effective set of Hv satisfying |Sv| ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|). If u = v, then |NG◦H(u) ∩ S| = |NG(u) ∩ S|+ |Sv| ≤ |NG(u) ∩ S|+ n+ |NG(v) \ S| − |NG(u) ∩ S| − |Sv| = |NG(v) \ S|+ |V (Hv) \ Sv| F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 988 = |NG◦H(u) \ S|. If u ∈ Sv, then |NG◦H(u) ∩ S| = |NHv(u) ∩ Sv| ≤ |NHv(u) \ Sv| = |NG◦H(u) \ S|. Now, suppose that v /∈ S. Then, by Property (ii), Sv = S ∩ V (Hv) is a K1-cost effective dominating set of Hv. Since NG◦H(u)∩S = NHv+v(u)∩Sv and NG◦H(u)\S = NHv+v(u)\ Sv, the desired inequality follows. Therefore, S is a cost effective set of G ◦H. Remark 5. The conclusion in Theorem 6 still holds even if the graph H contains an isolated vertex. Suppose that u is an isolated vertex of H. For v ∈ S∩V (G), u /∈ S∩V (Hv). In fact, if H is an empty graph, then S ∩V (Hv) = ∅ which is a cost effective set, and the claim in the necessity part holds. Lemma 2. Let G be an isolate-free graph. Every cost effective set of maximum cardinality is a dominating set of G. Proof. Let S ⊆ V (G) be a cost effective set of G of maximum cardinality. Suppose that S is not a dominating set of G, and let v ∈ V (G) \NG[S]. Define S∗ = S ∪ {v}. For each u ∈ S, NG(u)∩S∗ = NG(u)∩S and NG(u) \S∗ = NG(u) \S so that |NG(u)∩S∗| ≤ |NG(u) \ S∗|. We also have |NG(v) ∩ S∗| = 0 ≤ |NG(v) \ S∗|. Thus, S∗ is a cost effective set of G, contradicting the assumption on S being a cost effective set of maximum cardinality. Therefore, S is a dominating set of G. Corollary 6. Let G and H be nontrivial connected graphs of orders m and n, respectively. Then (i) γce(G ◦H) = mγK1ce(H)− (γK1ce(H)− 1) γ+Knce (G) whenever ∆(G) > n; (ii) γmce(G ◦H) = mγK1mce(H); and (iii) mγ+K1ce (H) ≤ γ+ce(G ◦ H) ≤ |L| + mγ+K1ce (H), where L = {v ∈ V (G) : degG(v) ≥ 2γ+K1ce (H)− n}. Proof. Let D ⊆ V (G) be a γ+Knce set of G. Note that if ∆(G) > n, then D 6= V (G).For each v ∈ V (G) \D, let Sv ⊆ V (Hv) be a γK1ce-set of Hv. Put S = D ∪ ( ⋃ v∈V (G)\D Sv ) . For each v ∈ S ∩ V (G) = D, S ∩ V (Hv) = ∅ so that |S ∩ V (Hv)| = 0 ≤ |V (H)|+ |NG(v) \ S| − |NG(v) ∩ S|. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 989 For each v ∈ V (G) \ S = V (G) \D, Sv = S ∩ V (Hv) is a K1-cost effective dominating set of Hv. By Theorem 6, S is a cost effective dominating set of G ◦H, and γce(G ◦H) ≤ |S| = |D|+ ∑ v∈V (G)\D |Sv| = γ+Knce (G) + ( |V (G)| − γ+Knce (G) ) γK1ce(H) = |V (G)|γK1ce(H)− (γK1ce(H)− 1) γ+Knce (G). Conversely, let S ⊆ V (G ◦H) be a γce-set of G ◦H. In view of Theorem 6 we can write |S| = ∑ v∈S∩V (G) (1 + |S ∩ V (Hv)|) + ∑ v∈V (G)\S γK1ce(H). Now S can be made as small as desired if S ∩ V (Hv) can be made ∅ for all v ∈ S ∩ V (G). This is attained when S∩V (G) is a Kn-cost effective set of G so that |S∩V (G)| ≤ γ+Knce (G) and |V (G) \ S| ≥ |V (G)| − γ+Knce (G) by Lemma 2. Therefore, γce(G ◦H) = |S| = |S ∩ V (G)|+ ∑ v∈V (G)\S γK1ce(H) ≥ γ+Knce (G) + ( |V (G)| − γ+ce(G) ) γK1ce(H) This proves Statement (i). To prove Statement (ii), let S = ⋃ v∈V (G) Sv, where Sv ⊆ V (Hv) is a γK1mce-set of Hv for each v ∈ V (G). By Theorem 6, S is a cost effective dominating set of G ◦ H. Since Sv is a minimal cost effective dominating set of Hv + v for each v ∈ V (G), S is a minimal cost effective dominating set of G ◦H. Thus, γmce(G ◦H) ≥ |S| = |V (G)|γK1mce(H). Conversely, let S ⊆ V (G ◦ H) be a γmce-set of G ◦ H. Let v ∈ V (G) \ S. By Theorem 6(ii) and the minimality of S, S ∩ V (Hv) is a minimal K1-cost effective dominating set of Hv. Let v ∈ S ∩ V (G). By Theorem 6(i), Sv = S ∩ V (Hv) is a cost effective set of Hv satisfying |Sv| ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|) < n 2 . Thus, |NG(v) ∩ S| ≤ |NG(v) ∩ S|+ 2|Sv| = |NG◦H(v) ∩ S|+ |Sv| ≤ |NG◦H(v) \ S|+ |Sv| = |NG(v) \ S|+ n. Let S∗ = S \ Sv. Since v dominates V (Hv + v), S∗ is a dominating set of G ◦ H. Note that each u ∈ S∗ \ {v} is cost effective relative to S∗ as it is relative to S in G ◦H. Now, |NG◦H(v) ∩ S∗| = NG(v) ∩ S| F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 990 ≤ |NG(v) \ S|+ n = |NG◦H(v) \ S∗|. Since S is minimal, S = S∗, and Sv = ∅. Since v is arbitrary, γmce(G ◦H) = |S| = ∑ v∈S∩V (G) |S ∩ V (Hv + v)|+ ∑ v∈V (G)\S |S ∩ V (Hv)| ≤ ∑ v∈V (G) γK1mce(H). Finally, we prove Statement (iii). For each v ∈ V (G), let Sv ⊆ V (Hv) be a γ+K1ce -set of Hv. By Proposition 3, S = ∪v∈V (G)Sv is a cost effective dominating set of G ◦H. Thus γ+ce(G ◦H) ≥ mγ+K1ce (H). Now, suppose that γ+ce(G ◦ H) > mγ+K1ce (H), and let S ⊆ V (G ◦ H) be a γ+ce-set of G ◦H. Then there exists v ∈ S ∩ V (G) such that |S ∩ V (Hv + v)| = 1 + γ+K1ce (H). Thus, Sv = S ∩ V (Hv) is a very cost effective set of Hv of cardinality γ+K1ce (H) and satisfying γ+K1ce (H) ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|) ≤ 1 2 (n+ degG(v)) . In other words, degG(v) ≥ 2γK1ce + (H)− n. Thus, v ∈ L. Therefore, γ+ce(G ◦H) ≤ |L| ( 1 + γ+K1ce (H) ) + (m− |L|) γ+K1ce (H) = |L|+mγ+K1ce (H). Remark 6. The bounds in Corollary 4.2.10 are sharp. Note, for example that γ+ce(P3 ◦K4) = 9 = 3γ+K1ce (K4). Verify also that γ+ce(P3 ◦K1,3) = 10 = 1 + 3γ+K1ce (K1,3). Corollary 7. Let G be a connected graph and m ≥ 2. Then (i) γce(G ◦Km) = |V (G)|; (ii) γmce(G ◦Km) = |V (G)|; and (iii) γ+ce(G ◦Km) = |V (G)| ⌊ m+2 2 ⌋ . Proof. Statement (i) follows from Corollary 5 and Corollary 6. Corollary 6 also yields Statement (ii) and Statement (iii) and the fact that γK1ce(Km) = 1, γK1mce(Km) = 1 and γ+K1ce (Km) = ⌊ m+2 2 ⌋ . F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 991 Example 3. If G is either the path Pn or the cycle Cn of order n and m ≥ 2, then (i) γce(G ◦Km) = n; (ii) γmce(G ◦Km) = n; and (iii) γ+ce(G ◦Km) = n ⌊ m+2 2 ⌋ . Example 4. For the complete graph Kn of order n ≥ 2 and m ≥ 2, (i) γce(Kn ◦Km) = n; (ii) γmce(Kn ◦Km) = n; and (iii) γ+ce(Kn ◦Km) = n ⌊ m+2 2 ⌋ . Proposition 5. Let G be a connected graph and H the union of k isolated vertices and K isolate-free subgraph. Then (i) γce(G ◦H) = |V (G)| (k + γK1ce(K))− γ+Knce (G) (γK1ce(K) + k − 1); (ii) γmce(G ◦H) = |V (G)| (k + γK1mce(K)); and (iii) γ+ce(G ◦H) = |V (G)| ( k + γ+K1ce (K) ) . Proof. Let D ⊆ V (G) be a Kn-cost effective set of G of maximum cardinality. For each v ∈ D, define Sv = {v}, and for each v ∈ V (G) \ D, let Sv = ( Lv ∪ Pv ) ⊆ V (Hv) where Lv = ∪ki=1{ui} be the union of k isolated vertices and Pv ⊆ V (Kv) be a γK1ce-set of Kv. Put S = ∪v∈V (G)Sv. For each v ∈ S ∩ V (G) = D, S ∩ V (Hv)| = ∅ so that |S ∩ V (Hv)| = 0 ≤ |V (H)|+ |NG(v) \ S| − |NG(v) ∩ S|. For each v ∈ V (G) \ S = V (G) \D, S ∩ V (Hv) = Sv is a K1-cost effective dominating set of Hv. By Remark 6, S is a cost effective dominating set of G ◦H, and γce(G ◦H) ≤ |S| = |D|+ ∑ v∈V (G)\D |Sv| = γ+Knce (G) + ( |V (G)| − γ+Knce (G) ) (k + γK1ce(K)) = |V (G)| (k + γK1ce(K))− (γK1ce(K) + k − 1) γ+Knce (G). Conversely, let S ⊆ V (G ◦H) be a γce-set of G ◦H. In view of Theorem 6 we can write |S| = ∑ v∈S∩V (G) (1 + |S ∩ V (Hv)|) + ∑ v∈V (G)\S γK1ce(K) + k. Now S can be made as small as desired if S ∩ V (Hv) can be made ∅ for all v ∈ S ∩ V (G). This is attained when S∩V (G) is a Kn-cost effective set of G so that |S∩V (G)| ≤ γ+Knce (G) and |V (G) \ S| ≥ |V (G)| − γ+Knce (G). Therefore, γce(G ◦H) = |S| = |S ∩ V (G)|+ ∑ v∈V (G)\S (γK1ce(K) + k) F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 992 ≥ γ+Knce (G) + ( |V (G)| − γ+Knce (G) ) (k + γK1ce(K)) = |V (G)| (k + γK1ce(K))− γ+Knce (G) (γK1ce(K) + k − 1) This proves Statement (i). To prove Statement (ii), let H be of order n and S = ∪v∈V (G)Sv, where Sv = Lv∪Pv ⊆ V (Hv) is a γK1mce-set of Hv for each v ∈ V (G), with Lv = ∪ki=1{ui} a union of k isolated vertices and Pv ⊆ V (Kv) be a γK1mce-set of Kv. By Theorem 6, S is a cost effective dominating set of G ◦H. Since Sv is a minimal cost effective dominating set of Hv + v for each v ∈ V (G), S is a minimal cost effective dominating set of G ◦H. Thus, γmce(G ◦H) ≥ |S| = |V (G)| (k + γK1mce(K)) . Conversely, let S ⊆ V (G ◦ H) be a γmce-set of G ◦ H. Let v ∈ V (G) \ S. By Theorem 6(ii) and the minimality of S, S ∩ V (Hv) is a minimal K1-cost effective dominating set of Hv. Let v ∈ S ∩ V (G). If v is cost effective relative to S ∩ V (G), then the minimality of S implies that S ∩ V (Hv + v) = {v}. Suppose that v is not cost effective relative to S ∩ V (G). By Theorem 6(i), Sv = S ∩ V (Hv) is a cost effective set of Hv satisfying |Sv| ≤ 1 2 (n+ |NG(v) \ S| − |NG(v) ∩ S|) < n 2 . Thus, |NG(v) ∩ S| ≤ |NG(v) ∩ S|+ 2|Sv| = |NG◦H(v) ∩ S|+ |Sv| ≤ |NG◦H(v) \ S|+ |Sv| = |NG(v) \ S|+ n. Let S∗ = S \ Sv. Since v dominates V (Hv + v), S∗ is a dominating set of G ◦H. Clearly, each u ∈ S∗ \ {v} is cost effective relative to S∗ as it is relative to S in G ◦H. Now, |NG◦H(v) ∩ S∗| = NG(v) ∩ S| ≤ |NG(v) \ S|+ n = |NG◦H(v) \ S∗|. Since S is minimal, S = S∗, and Sv = ∅. Thus, γmce(G ◦H) = |S| = ∑ v∈S∩V (G) |S ∩ V (Hv + v)|+ ∑ v∈V (G)\S |S ∩ V (Hv)| ≤ ∑ v∈V (G) (k + γK1mce(K)) = |V (G)| (k + γK1mce(K)) . Finally, we prove Statement (iii). For each v ∈ V (G), let Sv ⊆ V (Hv) be a γ+K1ce -set of Hv,with Sv = Lv ∪ Pv ⊆ V (Hv) where Lv = ∪ki=1{ui} is a union of k isolated vertices F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 993 and Pv ⊆ V (Kv) is a γ+K1ce -set of Kv. Then S = ∪v∈V (G)Sv satisfies the properties of Theorem 6, and thus is a cost effective dominating set of G ◦H. It follows that γ+ce(G ◦H) ≥ |S| = ∑ v∈V (G) Sv = |V (G)| ( k + γ+K1ce (K) ) . Conversely, suppose that S ⊆ V (G ◦H) is a γ+ce-set of G ◦H. Then, γ+ce(G ◦H) = |S| = ∑ v∈S∩V (G) S ∩ V (Hv + v) + ∑ v∈V (G)\S S ∩ V (Hv) ≤ γ+ce(G) ( γ+K1ce (K) + k ) + ( |V (G)| − γ+ce(G) ) ( γ+K1ce (K) + k ) ≤ γ+Knce (G) ( γ+K1ce (K) + k ) + ( |V (G)| − γ+Knce (G) ) ( γ+K1ce (K) + k ) = |V (G)| ( k + γ+K1ce (K) ) . 4. Composition of Graphs Theorem 7. [9] Let G and H be connected graphs. Then C = ⋃ x∈S ({x}×Tx) ⊆ V (G[H]), where S ⊆ V (G) and Tx ⊆ V (H) for every x ∈ S, is a dominating set of G[H] if and only if either (i) S is a total dominating set of G, or (ii) S is a dominating set of G and Tx is a dominating set of H for every x ∈ S \NG(S). Theorem 8. [9] Let G and H be nontrivial connected graphs with γ(H) = 1. Then γ(G[H]) = 1. Remark 7. Let G and H be connected graphs. For C = ∪u∈S ({x} × Tx) ⊆ V (G[H]) and (u, v) ∈ C, |NG[H]((u, v)) ∩ C| = ∑ x∈S∩NG(u) |Tx|+ |NH(v) ∩ Tu| (2) and |NG[H]((u, v)) \ C| = |NG(u) \ S||V (H)|+ |NH(v) \ Tu|+ ∑ x∈NG(u)∩S |V (H) \ Tx| (3) It is worth noting that a graph may not have a total dominating set that is cost effective. A good example is the path P3. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 994 Theorem 9. Let G and H be nontrivial connected graphs, and C = ∪x∈S({x} × Tx) ⊆ V (G[H]), where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S. If S is an independent dominating set of G and Tx is a dominating set of H for each x ∈ S, then C is a cost effective dominating set of G[H]. Proof. Suppose that S is an independent dominating set of G and Tx is a dominating set of H for each x ∈ S. By Theorem 7, C is a dominating set of G[H]. Let u ∈ S and v ∈ Tu. Since G is nontrivial and S is independent, NG(u) \ S 6= ∅. Using Equations 2 and 3, |NG[H](u, v) ∩ C| = |NH(v) ∩ Tu| < |NH(v) \ Tu|+ |NG(u) \ S||V (H)| = |NG[H]((u, v)) \ C|. Since u and v are arbitrary, C is a cost effective dominating set of G[H]. Corollary 8. For any nontrivial connected graphs G and H, γce(G[H]) ≤ γi(G)γ(H). Corollary 9. For any nontrivial connected graphs G and H with G claw-free, γce(G[H]) = γ(G)γ(H). Theorem 10. Let G and H be nontrivial connected graphs, and let C = ∪x∈S({x}×Tx) ⊆ V (G[H]). If C has the following properties: (i) S is a cost effective dominating set of G; (ii) For each x ∈ S \NG(S), Tx is a dominating set of H; and (iii) For each x ∈ S ∩NG(S), Tx is a cost effective set of H, then C is a cost effective dominating set of G[H]. Proof. By Theorem 7, properties (i) and (ii) imply that C is a dominating set of G[H]. Let (x, y) ∈ C. Suppose that x ∈ S \NG(S). Then NG(x) \ S 6= ∅. Following Equations 2 and 3, |NG[H]((x, y)) ∩ C| = |NH(y) ∩ Tx| < |NG(x) \ S||V (H)|+ |NH(y) \ Tx| = |NG[H]((x, y)) \ C|. Suppose that x ∈ S ∩NG(S). Properties (i) and (iii) and Equations 2 and 3 yield |NG[H]((x, y)) ∩ C| = ∑ x∈S∩NG(u) |Tx|+ |NH(y) ∩ Tx| ≤ |S ∩NG(x)||V (H)|+ |NH(y) ∩ Tx| F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 995 ≤ |NG(x) \ S||V (H)|+ |NH(y) \ Tx|+ ∑ z∈NG(x)∩S |V (H) \ Tz| = |NG[H]((x, y)) \ C|. Accordingly, C is a cost effective dominating set of G[H]. Removing the condition that S is a cost effective set of G in Theorem 10(i) may not yield a cost effective dominating set C of G[H]. Consider, for example, the set C = V (K3) × U in the composition G = K3[K1,4], where U is the partite set of K1,4 with |U | = 4. For each x ∈ V (K3) and u ∈ U , |NG((x, u)) ∩ C| = 8, and |NG((x, u)) \ C| = 3. Thus, C is not a cost effective set, hence not a cost effective dominating set, of G. Next, let S◦ = S ∩NG(S). Theorem 11. For all nontrivial connected graphs G and p ≥ 2, (i) γce(G[Kp]) = γ(G); (ii) γmce(G[Kp]) = γmce(G); and (iii) γ+ce(G[Kp]) ≥ max{p|S| − ( p− ⌊ p+1 2 ⌋) |S◦| : S is a γ+ce − set of G}. Proof. Let S ⊆ V (G) be a γ-set of G, and let v ∈ V (Kp). Define C = S × {v}. By Theorem 7, C is a dominating set of G[Km]. For each u ∈ S, |NG[Kp]((u, v)) ∩ C| = |NG(u) ∩ S| ≤ p|NG(u) \ S|+ (p− 1) + (p− 1)|NG(u) ∩ S| = |NG[Kp]((u, v)) \ C|. Thus, C is a cost effective dominating set of G[Kp] so that γce(G[Kp]) ≤ |S| = γ(G). By Theorem 8, γce(G[Kp]) = γ(G). Suppose that S is a γmce-set of G. By Theorem 10, C = S × {v} is a cost effective dominating set of G[Kp]. Let (u, v) ∈ C, and put C∗ = C \ {(u, v)}. Then C∗ = S∗×{v}, where S∗ = S \ {u}. Let w ∈ S∗. If u /∈ NG(w), then |NG(w) ∩ S∗| = |NG(w) ∩ S| ≤ |NG(w) \ S| = |NG(w) \ S∗|. If u ∈ NG(w), then |NG(w) ∩ S∗| = |NG(w) ∩ S| − 1 < |NG(w) \ S|+ 1 = |NG(w) \ S∗|. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 996 That is, S∗ is a cost effective set of G. Since S is a minimal cost effective dominating set of G, S∗ is not a dominating set of G. By Theorem 7, C∗ is not a dominating set, hence not a cost effective dominating set, of G[Kp]. This shows that C is a minimal cost effective dominating set of G ◦H. Thus, γmce(G[Kp]) ≥ |C| = |S| = γmce(G). Conversely, suppose that C = ∪u∈S ({u} × Tu) ⊆ V (G[Kp]) is a minimal cost effective dominating set of G[Kp]. We claim that |Tu| = 1 for each u ∈ S. Suppose that |Tu| ≥ 2 for some u ∈ S. Let C∗ = C \ {(u, x)}, where x ∈ Tu, and let v ∈ Tu \ {x}. Since the G-projection C∗G = S and every subset of V (Kp) is dominating of Kp, C ∗ is dominating of G[Kp] by Theorem 7. In view of Equations (1) and (2), |NG[Kp]((u, v)) ∩ C∗| ≤ |NG[Kp]((u, v)) ∩ C|, and |NG[Kp]((u, v)) \ C∗| ≥ |NG[Kp]((u, v)) \ C|. Thus, C∗ is a cost effective set of G[Kp]. Consequently, C∗ is a cost effective dominating set of G[Kp], a contradiction. Thus |Tu| = 1 for all u ∈ S. In view of the proof of the necessity part of the statement, we may assume that for some v ∈ V (Kp), Tu = {v} for all u ∈ S. Clearly, the minimality of C implies that S is a minimal cost effective dominating set of G. Thus, γmce(G) ≥ |S| = |C|. Since C is arbitrary, γmce(G) ≥ γmce(G[Kp]). Now, let S ⊆ V (G) be a γ+ce-set of G. For each u ∈ S ∩ NG(S), let Tu ⊆ V (Kp) be a γ+ce-set of Kp, and for each u ∈ S \ NG(S), let Tu = V (Kp). By Theorem 10, C = ∪u∈S ({u} × Tu) is a cost effective dominating set of G[H]. Thus, γ+ce(G[Km]) ≥ |C| = |S◦|γ+ce(Kp) + (|S| − |S◦|) |V (Kp)|. Following a similar proof shows that if G and H are nontrivial connected graphs with γ(H) = 1, γmce(G[H]) = γce(G[H]) = γ(G). Theorem 12. Let G be a noncomplete connected graph and p ≥ 3. Then (i) γce(Kp[G]) =  1, if γ(G) = 1 2, otherwise. (ii) γmce(Kp[G]) = γm(G); and (iii) γ+ce(Kp[G]) = ⌊ p+1 2 ⌋ |V (G)|. Proof. Let x, y ∈ V (Kp) be distinct and u ∈ V (G). By Theorem 10, C = {x, y} × {v} is a cost effective dominating set of Kp[G]. Thus, γce(Kp[G]) ≤ |C| = 2. F.Jamil, H. Nuenay-Maglanque / Eur. J. Pure Appl. Math, 12 (3) (2019), 978-998 997 Also, by Theorem 10, for any x ∈ V (Kp) and any dominating set S ⊆ V (G) of G, C = {x}×S is a cost effective dominating set of Kp[G]. Thus, γce(Kp[G]) = min{γ(G), 2}, and the conclusion follows. To prove Statement (ii), note first that since G is not complete, γm(G) ≥ 2. Let S ⊆ V (G) be a minimal dominating set of G and x ∈ V (Kp). In view of Theorem 7, C = {x} × S is a minimal cost effective dominating set of Kp[G]. Consequently, γmce(Kp[G]) ≥ |C| = |S|. Since S is arbitrary, γmce(Kp[G]) ≥ γm(G). Conversely, let C = ∪u∈S ({u} × Tu) ⊆ V (Kp[G]) be a γmce-set of Kp[G]. Since C is a dominating set of Kp[G], either S ia total dominating set of Kp or S is a dominating set of Kp, in which case Tu is a dominating set for each u ∈ S \ NKp(S). Since C is minimal, if S is a total dominating set in Kp, then C = {(x, y), (u, v)} for some x, u ∈ V (Kp). On the other hand, if S is not a total dominating set, then C = {x}×S for some x ∈ V (Kp) and S is a minimal dominating set of G. Thus, γmce(Kp[G]) ≤ max{2, γm(G)} = γm(G). This proves Statement (ii). To prove Statement (iii), let C = ∪u∈S ({u} × V (G)), where S ⊆ V (Kp) ia a γ+ce-set in Kp. By Theorem 10, C is a cost effective dominating set of Kp[G]. Consequently, γ+ce(Kp[G]) ≥ |S| × |V (G)|. Conversely, let C = ∪u∈S ({u} × Tu) be a γ+ce-set of Kp[G]. In view of Theorem 10, since we want the largest possible cardinality of C, we assume that Tu = V (G), which is a dominating set of G. Let u ∈ S. Equation 2 and Equation 3, respectively, yield |NKp[G]((u, v)) ∩ C| = |NKp(u) ∩ S||V (G)|+ |NG(v) ∩ V (G)| = (|S| − 1) |V (G)|+ |NG(v)|. and |NKp[G]((u, v)) \ C| = |NKp(u) \ S||V (G)| = (p− |S|) |V (G)|. for each v ∈ V (G) . Since C is a cost effective set of Kp[G], (|S| − 1) |V (G)|+ |NG(v)| ≤ (p− |S|) |V (G)|, or equivalently, 2|S||V (G)| ≤ (p+ 1)|V (G)| − |NG(v)| for each v ∈ V (G). Thus, |S| < 1 2 (p+ 1). Therefore, γ+ce(Kp[G]) = |C| = |S||V (G)| ≤ ⌊ p+ 1 2 ⌋ |V (G)|, and the desired conclusion follows. REFERENCES 998 References [1] Buckley, Fred and Frank Harary, Distance in Graphs, Redwood City, CA: Addison- Wesley, 1990. [2] C. Berge, Theory of Graphs and its Applications, Methuen, London, 1962 [3] J.A. Bondy and Geng-hau Fan, A sufficient condition for dominating cycles, Discrete Math, Vol. 67(2): 205-208, 1987 [4] E.J. Cockayne and S.T. Hedetniemi, Towards a Theory of Domination in Graphs. Networks, 7(3): 247-261, 1997. [5] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, Inc. New York (1998). [6] T. Haynes, S. Hedetniemi and M. Henning, Domination in graphs applied to electrical power networks, J. Discrete Math, Vol. 15(4), 2000. [7] O. Ore, Theory of Graphs, Amer. Math. Soc. Transl., 38 (Amer. Math. Soc., Privi- dence, RI, 1962), 206-212. [8] S. Canoy Jr, and C. Go, Domination in the join and corona of graphs, International Mathematical Forum, Vol. 6(16): 763 - 771, 2011. [9] S. Canoy Jr, and C. Go, Domination in the composition of graphs, AKCE Journal of Graph Theory, to appear. [10] F.V. Fomin, F. Gradoni, A. Pyatkin and A. Stepanov, On maximum number of min- imal dominating sets in graphs, Discrete Mathematics, 22:157-162, 2005. [11] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, T.L. McCoy, I. Vasylieva, Cost effective domination in graphs, Cong. Numer., Vol 211 (2012), 197 - 209. [12] T.W. Haynes, S.T. Hedetniemi, T.L. McCoy and T.K. Rodriguez, Bounds on cost effective domination numbers, Quaestiones Mathematicae, Vol. 39(6): 773-783, 2016. [13] H. Nuenay and F. Jamil On the minimal geodetic domination in graphs, Discussiones Mathematicae,Graph theory. Vol.45, 403-418, 2015.