EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 14, No. 2, 2021, 537-550 ISSN 1307-5543 – ejpam.com Published by New York Business Global Minimal and Upper Cost Effective Domination Number in Graphs Hearty M. Nuenay- Maglanque1,∗, Ferdinand P. Jamil2 1 Department of Applied Mathematics, College of Science and Mathematics, University of Science and Technology of Souther Philippines, 9000 Cagayan de Oro City, Philippines 2 Department of Mathematics and Statistics, College of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. Given a connected graph G, we say that S ⊆ V (G) is a cost effective dominating set in G if, each vertex in S is adjacent to at least as many vertices outside S as inside S and that 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, and is denoted by γ+ce(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, and is denoted by γmce(G). In this paper we provide bounds on upper cost effective domination number and minimal cost effective domination number of a connected graph G and characterized those graphs whose upper and minimal cost effective domination numbers are either 1, 2 or n− 1. We also establish a Nordhaus-Gaddum type result for the introduced parameters and solve some realization problems. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: cost effective dominating set, minimal cost effective dominating set, minimal cost effective domination number, upper cost effective domination number 1. Introduction Throughout this paper, we consider simple, finite and undirected graphs G = (V (G), E(G)). All basic terminologies used here are taken from [4]. For a sub- set S ⊆ V (G), the symbol |S| refers to the cardinality of S. In particular, |V (G)| is the order of G. Let G be a connected graph. For v ∈ V (G), the closed neighborhood of v is the set NG[v] consisting of v and all vertices adjacent to v. The open neighborhood of v is the set ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v14i2.3955 Email addresses: hearty.nuenay@ustp.edu.ph (H. Nuenay-Maglanque), ferdinand.jamil@gmsuiit.edu.ph (F. Jamil) http://www.ejpam.com 537 c© 2021 EJPAM All rights reserved. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 538 NG(v) = NG[v] \ {v}. For S ⊆ V (G), NG[S] = ∪v∈SNG[v] and NG(S) = ∪v∈SNG(v). S is said to be a dominating set in G if NG[S] = V (G). The minimum cardinality γ(G) of a dominating set is called the domination number of G. A dominating set S in 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 subset S ⊆ V (G) is an independent set in G if uv /∈ E(G) for distinct pairs of vertices u and v in S. An independent dominating set in G is an independent set in G which is dominating in G. The minimum cardinality γi(G) of an independent dominating set in G is called independence domination number. A subset S ⊆ V (G) is said to be a cost effective set in 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 in 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 in G if S is both a (very) cost effective set and a dominating set in G. The minimum cardinality of a cost effective dominating set of a graph G is called the cost effective domination number of G, and is denoted by γce(G). Motivated by [8], the following concepts are introduced by the authors in [7] . The maximum cardinality, denoted by γ+ce(G), of a cost effective dominating set in G is called an upper cost effective domination number of G. A cost effective dominating set of cardinality γ+ce(G) is called an upper cost effective dominating set. A cost effective dominating set S ⊆ V (G) is said to be minimal cost effective set if S does not contain a proper subset which is itself a cost effective dominating set. The symbol γmce(G) is used to denote the maximum cardinality of a minimal cost effective dominating set of G. For convenience, we use the terms γce-set, γ+ce-set and γmce-set to refer to the cost effective dominating sets with cardinality γce(G), γ+ce(G) and γmce(G), respectively. The following results are due to T.W. Haynes et.al. and F.V. Fomin et.al. Theorem 1. [2] For a connected graph G of order n ≥ 2, γce(G) ≤ ⌊ n 2 ⌋ . Theorem 2. [2] Let G be a connected graph (i) If ∆(G) ≤ 4, then γ(G) = γce(G). (ii) If γ(G) ≤ 3, then γ(G) = γce(G). Lemma 1. [2] Every independent dominating set in an isolate-free graph G is a very cost effective dominating set in G. Theorem 3. [5] Every maximal independent set is a minimal dominating set. 2. Results Proposition 1. Let C1, C2, . . . , Cn be the components of a graph G, and let S ⊆ V (G). Then S is a cost effective dominating set in G if and only if Sk = S ∩ V (Ck) is a cost effective dominating set in Ck for k = 1, 2, . . . , n. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 539 Proof. It is clear that S is a dominating set in G if and only if Sk is a dominating set in Ck for each k = 1, 2, . . . , n. Moreover, since for v ∈ Sk, we have NG(v) ∩ S = NCk ∩ Sk and NG(v) \ S = NCk (v) \ Sk, S is a cost effective set in G if and only if Sk is a cost effective set in Ck for each k = 1, 2, . . . , n. Corollary 1. Let G be a graph of order n. Then γce(G) = n if and only if G = Kn. Proof. Suppose that γce(G) = n. Then S = V (G) is the only cost effective set in G. Let u, v ∈ V (G) with u 6= v. Since NG(v) \ S = ∅, |NG(v) ∩ S| ≤ |NG(v) \ S| = 0. Consequently, |NG(v)∩S| = 0, that is, NG(v)∩S = ∅. Thus, u /∈ NG(v) so that uv /∈ E(G). Since u and v are arbitrary, G = Kn. The converse follows immediately from Proposition 1. Lemma 2. Let G be a nontrivial connected graph, and S ⊆ V (G). If S is a cost effective set in G, then every subset of S is also a cost effective set in G. Proof. If S = ∅, then the conclusion is trivial. Suppose that S ⊆ V (G) is a nonempty cost effective set in G. Let u ∈ S and put S∗ = S \ {u}. Let v ∈ S∗. If u ∈ NG(v), then NG(v) ∩ S∗ = (NG(v) ∩ S) \ {u} and NG(v) \ S = (NG(v) \ S∗) \ {u} so that |NG(v) ∩ S∗| < |NG(v) ∩ S| ≤ |NG(v) \ S| < |NG(v) \ S∗|. If u /∈ NG(v), then NG(v) ∩ S∗ = NG(v) ∩ S and NG(v) \ S∗ = NG(v) \ S so that |NG(v) ∩ S∗| ≤ |NG(v) \ S∗|. This shows that S∗ is a cost effective set. If A ( S, then A can be obtained from S by removing one vertex at a time. As shown above, removal of a vertex from a cost effective set results to a cost effective set. Thus, A is a cost effective set in G. Corollary 2. Let G be a nontrivial connected graph. Then every minimal cost effective dominating set in G is a minimal dominating set. Consequently, γmce(G) ≤ γm(G). H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 540 Remark 1. A minimal dominating set need not be a minimal cost effective dominating set. Remark 2. Any independent dominating set in a connected nontrivial graph is a minimal cost effective dominating set in G. Corollary 3. Let G be a nontrivial connected graph . Then i(G) ≤ γmce(G) ≤ γm(G). Proof. This follows from Remark 2 and Corollary 2. Remark 3. For any nontrivial connected graph G, γce(G) ≤ γmce(G) ≤ γ+ce(G). Theorem 4. For any connected graph G of order n ≥ 2, if G is not complete, then γmce(G) ≥ 2, and consequently, γ+ce(G) ≥ 2. Proof. Let S be a maximal independent set of G. Since G 6= Kn, |S| > 2. By Theorem 3, S is a dominating set in G. Thus, S is a minimal cost effective dominating set in G by Corollary 2. Consequently, γmce(G) ≥ 2. Theorem 5. For any complete graph Kn of order n ≥ 2, γ+ce(Kn) = ⌊ n+ 1 2 ⌋ . Proof. Let S ⊆ V (Kn) with |S| = ⌊ n+1 2 ⌋ . For each u ∈ S, |NKn(u) ∩ S| = |S| − 1 = ⌊ n+ 1 2 ⌋ − 1 and |NKn(u) \ S| = n− |S|. Now, 2 ⌊ n+1 2 ⌋ ≤ n+ 1 so that |NKn(u) ∩ S| = ⌊ n+ 1 2 ⌋ − 1 ≤ n− ⌊ n+ 1 2 ⌋ = |NKn(u) \ S|. Thus, S is a cost effective dominating set in Kn. Hence, γ+ce(Kn) ≥ |S| = ⌊ n+ 1 2 ⌋ . Let S be a γ+ce-set of Kn. For each u ∈ S, |NKn(u) ∩ S| = |S| − 1 and |NKn(u) \ S| = |V (Kn) \ S| = |V (Kn)| − |S| = n− |S|. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 541 Since S is cost effective, |S| − 1 ≤ n− |S|, or equivalently, 2|S| ≤ n+ 1. Thus, |S| ≤ 1 2(n+ 1). Since S is a γ+ce-set, γ+ce(Kn) = |S| = ⌊ n+ 1 2 ⌋ . Corollary 4. Let G be a nontrivial connected graph of order n ≥ 2. Then (i) γce(G) = 1 if and only if G = K1 +H for some subgraph H of G; (ii) γmce(G) = 1 if and only if G = Kn; (iii) γ+ce(G) = 1 if and only if G = K2. Proof. Statement (i) is clear, while statement (ii) follows immediately from Theorem 4. Suppose that γ+ce(G) = 1. Then G is complete, by Theorem 4. Now, γ+ce(Kn) = ⌊ n+1 2 ⌋ by Theorem 5. Thus, γ+ce(Kn) = 1 if and only if n = 2. Theorem 6. For m,n ≥ 1, (i) γce(Km,n) = min {m,n, 2} (ii) γmce(Km,n) = γ+ce(Km,n) = max {m,n} . Proof. The result is obvious if n = 1 or m = 1. Suppose that m,n ≥ 2. Put G = Km,n. We claim that S ⊆ V (G) is a cost effective dominating set in G if and only if either S is a partite set of Km,n or S intersects each partite set and 2 ≤ |S| ≤ ⌊ n 2 ⌋ + ⌊ m 2 ⌋ . Since partite sets U, V of Km,n are independent dominating sets of G, they are minimal cost effective dominating sets in G by Proposition 2. Assume |U | = m and |V | = n. Let S be a cost effective dominating set in G which is not a partite set. Since S is a dominating set, S intersects both partite sets. Let v ∈ S. If v ∈ U , then |S ∩ V | = |NG(v) ∩ S| ≤ |NG(v) \ S| = |V \ S|. Consequently, |S ∩ V | ≤ ⌊ n 2 ⌋ . Similarly, |S ∩ U | ≤ ⌊ m 2 ⌋ . Thus, 2 ≤ |S| ≤ ⌊ n 2 ⌋ + ⌊ m 2 ⌋ . The converse is obvious. Therefore, γce(G) = min{m,n, 2} = 2 and γmce(G) = max{m,n} = γ+ce(G). Theorem 7. (i) For n ≥ 2, γ+ce(Pn) = ⌊ 2n 3 ⌋ and γmce(Pn) = ⌈n 2 ⌉ . H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 542 (ii) For n ≥ 3, γ+ce(Cn) = ⌊ 2n 3 ⌋ and γmce(Cn) = ⌈ n− 1 2 ⌉ Proof. For (i), let Pn = [v1, v2, . . . , vn] be a path of order n ≥ 2. The result is clear if n = 2. Suppose that n ≥ 3, and let n = 3k + j, with k ≥ 1 and 0 ≤ j ≤ 2. Note that for j = 0, 1, the set {v1, v3, v4, . . . , v3k−3, v3k−2, v3k} is a cost effective dominating set in Pn. On the other hand, if j = 2, then set {v1, v3, v4, . . . , v3k−3, v3k−2, v3k, v3k+1} is a cost effective dominating set in Pn. In any case, γ+ce(Pn) ≥ ⌊ 2n 3 ⌋ . Now, let S ⊆ V (Pn) be a γ+ce-set in Pn. Being a cost effective dominating set, the vertices vi, vi+1, vi+2 cannot be all in S for all i = 1, 2, . . . , n − 2. In particular, if j = 0, then |S| ≤ 2k, and this is attained with v3k ∈ S. Apparently, in view of this, |S| ≤ 2k for j = 1 and |S| ≤ 2k + 1 for j = 2. Indeed, γ+ce(Pn) = ⌊ 2n 3 ⌋ . Similarly, to prove the second part of (i), we write n = 2k + j, with 0 ≤ j ≤ 1. Since the sets {v1, v3, v5, . . . , v2k−1} and {v1, v3, v5, . . . , v2k−1, v2k+1} are minimal cost effective dominating sets in Pn for j = 0 and j = 1, respectively, we have γmce(Pn) ≥ ⌈ n 2 ⌉ . Conversely, let S ⊆ V (Pn) be a minimal cost effective dominating set in Pn. Then for all i = 1, 2, . . . , n−3, |S∩{vi, vi+1, vi+2, vi+3}| ≤ 2. Thus, |S| ≤ ⌈ 2n 4 ⌉ = ⌈ n 2 ⌉ . For (ii), let Cn = [v1, v2, . . . , vn] be a cycle of order n ≥ 3. The result is clear if n = 3. Suppose that n ≥ 4, and let n = 3k+ j, with k ≥ 1 and 0 ≤ j ≤ 2. Note that for j = 0, 1, the set {v1, v3, v4, . . . , v3k−3, v3k−2, v3k} is a cost effective dominating set in Cn. On the other hand, if j = 2, then set {v1, v3, v4, . . . , v3k−3, v3k−2, v3k, v3k+1} is a cost effective dominating set in Cn. In any case, γ+ce(Cn) ≥ ⌊ 2n 3 ⌋ . Now, let S ⊆ V (Cn) be a γ+ce-set in Cn. This means that the vertices vi, vi+1, vi+2 cannot be all in S for all i = 1, 2, . . . , n− 2. In particular, if j = 0, then |S| ≤ 2k, and this is attained with v3k ∈ S. Apparently, in view of this, |S| ≤ 2k for j = 1 and |S| ≤ 2k + 1 for j = 2. Indeed, γ+ce(Cn) = ⌊ 2n 3 ⌋ . To prove the second part of (ii), we write n = 2k + j, with 0 ≤ j ≤ 1. Since the sets {v1, v3, v5, . . . , v2k−1} and {v1, v3, v5, . . . , v2k−2, v2k} are minimal cost effective dominating sets in Cn for j = 0 and j = 1, respectively, we have γmce(Cn) ≥ ⌈ n−1 2 ⌉ . Conversely, let S ⊆ V (Cn) be a minimal cost effective dominating set in Cn. Note that for any n ≥ 3, vn /∈ S. Also, for all i = 1, 2, . . . , n− 3, |S ∩ {vi, vi+1, vi+2, vi+3}| ≤ 2. Thus, |S| ≤ ⌈ n−1 2 ⌉ . Therefore, γmce(Cn) = ⌈ n−1 2 ⌉ . Proposition 2. For any double star graph Sr,s where r, s ≥ 1, (i) γce(Sr,s) = 2 (ii) γ+ce(Sr,s) = r + s = γmce(Sr,s). Proof. Let u and v be the two central vertices of G = Sr,s, and let U and V be the sets of all leaves adjacent to u and v, respectively, with |U | = r and |V | = s. Let S be a cost effective dominating set in G. Note that if u ∈ S, then U ∩ S = ∅ and if u /∈ S, then U ⊆ S. Similar statements apply if v ∈ S and V ∩ S = ∅. Thus, S is one of the following: (i) S = {u, v}, (ii) S = {u} ∪ V , (iii) S = {v} ∪ U , (iv) S = U ∪ V. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 543 Therefore, γce(G) = 2 and γ+ce(G) = |U |+ |V | = r + s. Note further that if u, v /∈ S, then S \ {x} is not a dominating set in G, hence not a cost effective dominating set in G for any x ∈ U ∪ V. This means that U ∪ V is a minimal cost effective dominating set in G. Therefore, γmce(G) = |U |+ |V | = r + s. Corollary 5. If G is any of the following graphs: Pn (n ≥ 2), Cn (n ≥ 3), Km,n (m,n ≥ 2), Kn (n ≥ 1) and Sr,s, then γmce(G) = γm(G). Theorem 8. Let G be a connected graph of order n ≥ 2. Then, (i.) γmce(G) = n− 1 if and only if G = K1,n−1 (ii.) γ+ce(G) = n− 1 if and only if G = K1 + t⋃ j=1 Krj , where 1 ≤ rj ≤ 2 and ∑ rj = n− 1. Proof. Let S ⊆ V (G) be a cost effective set with |S| = n − 1, and let v ∈ V (G) \ S. Since G is connected and S is cost effective, it follows that uv ∈ E(G) and |NG(u) ∩ S| ≤ 1 for all u ∈ S. If there exists w ∈ S such that |NG(w) ∩ S| = 1 then S′ = S \ {w} is a cost effective set dominating set in G. If S is a minimal cost effective set, then 〈S〉 = Kn−1. Thus, G = K1,n−1. Otherwise, G = K1 + t⋃ j=1 Krj , where 1 ≤ rj ≤ 2 and ∑ rj = n− 1. The converse is clear. Theorem 9. For a connected graph G of order n ≥ 5, γ+ce(G) ≥ 3. Proof. Suppose that G is a complete graph of order n ≥ 5. If S ⊆ V (G) is a γ+ce-set in G, then by Theorem 5, γ+ce(G) = |S| = ⌊ 1 2(n+ 1) ⌋ ≥ ⌊ 1 2(5 + 1) ⌋ = 3. Suppose that G is not complete. Then there exist u, v ∈ V (G) such that uv /∈ E(G). Then {u, v} is a cost effective set in G. Suppose that NG[{u, v}] 6= V (G). Let v1 ∈ V (G) \ NG[{u, v}] and put S1 = {u, v, v1}. If NG[S1] = V (G), then S1 is a cost effective dominating set in G. Suppose that NG[S1] 6= V (G). Let v2 ∈ V (G) \NG[S1] and put S2 = {u, v, v1, v2}. If NG[S2] = V (G), then S2 is a cost effective dominating set in G. Continuing in this manner, there exists a positive integer k ≥ 1 such that vk /∈ NG[Sk−1] and NG[Sk] = V (G) wth S0 = {u, v}. Thus, Sk is a cost effective dominating set in G. Consequently, γ+ce(G) ≥ 3. Suppose that NG[{u, v}] = V (G). Note that, since |V (G)| ≥ 5, G has at least three more vertices v1, v2 and v3 other than u and v. Further, since {u, v} is a dominating set in G, at least two vertices in V (G) \ {u, v} are adjacent to either u or v or both. Consider the following cases. Case 1 : Suppose that v1v2 /∈ E(G). Subcase 1 : Consider having v1, v2 being adjacent only to either u or v. Assume that v1 and v2 are adjacent to u. Since S∗ = {v1, v2, v} is a cost effective set in G, one can construct a cost effective dominating set S beginning with S∗ as done above. Consequently, |S| ≥ 3. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 544 Subcase 2 : Consider v1 being adjacent to both u and v and v2 being adjacent only to either u or v. Note that since {u, v} is a dominating set in G, v3 ∈ NG({u, v}). If v3 /∈ NG(v1) ∩NG(v2), then the set S∗ = {v1, v2, v3} is a cost effective set in G, and one can construct a cost effective dominating set S beginning with S∗. On the other hand, if v3 ∈ NG(v1) ∩NG(v2), then the set S = {u, v, v3} is a cost effective dominating set in G. Thus, |S| ≥ 3. Subcase 3 : Suppose that v1, v2 are both adjacent to u and v. If v3 ∈ NG(v1)∩NG(v2), then the set S∗ = {u, v, v3} is a cost effective dominating set in G. If v3 /∈ NG(v1)∩NG(v2), then one can start with the cost effective set S∗ = {v1, v,2 , v3} to construct a cost effective dominating set S in G. Case 2 : Suppose that v1v2 ∈ E(G). Subcase 1 : Suppose that v1, v2 are adjacent only to either u or v. Assume that v1, v2 are adjacent to u. Since the set S∗ = {v1, v2, v} is a cost effective set in G, one can construct a cost effective dominating set S in G starting with S∗. Clearly, |S| ≥ 3. Subcase 2 : Suppose that v1 is adjacent to both u and v and v2 is adjacent only to either u or v. Assume that v2 ∈ NG(u). Then the set S = {u, v, v2} is a cost effective dominating set in G. Subcase 3 : Suppose that v1, v2 are both adjacent to u and v. If v3 ∈ NG(v1)∩NG(v2), then the set S = {u, v, v2} is a cost effective dominating set in G. If v3 /∈ NG(v1)∩NG(v2), then the set S∗ = {v1, v2, v3} is a cost effective set in G, and one can construct a cost effective dominating set S in G starting with S∗. In both cases, γ+ce(G) ≥ 3. Corollary 6. If G is a connected graph of order n ≥ 3, then γ+ce(G) = 2 if and only if G is one of the following graphs: P3, P4, C3, C4, K4 or K2 +K2. Proof. Suppose that γ+ce(G) = 2 and let S = {u, v} be a γ+ce-set in G. Let D = V (G)\S. If |D| = 1, then either G = C3 or G = P3. If |D| = 2, then G is any of the following: P4, C4, K2 +K2, or K4. Suppose that |D| ≥ 3. Then |V (G)| ≥ 5. By Theorem 9, γ+ce(G) > 2, and the desired conclusion follows. For the converse, it is easy to verify that if G is one of the following graphs: P3, P4, C3, C4, K2 +K2, or K4, then γ+ce(G) = 2. Theorem 10. Let G be a connected noncomplete graph. (i) If γm(G) = 2, then γmce(G) = 2. (ii) If γmce(G) = 2, then for each pair of nonadjacent vertices u and v of G, {u, v} is a dominating set in G Proof. For (i), observe that by Theorem 4 and Corollary 2, 2 ≤ γmce(G) ≤ 2. Thus, γmce(G) = 2. To prove (ii), suppose that γmce(G) = 2 and let u, v ∈ V (G) with uv /∈ E(G). Then {u, v} is a cost effective set in G, and as previously done, one can H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 545 construct a minimal cost effective dominating set S in G beginning with the vertices u and v. Since γmce(G) = 2, |S| = 2 and S = {u, v}. Thus, S = {u, v} is a dominating set in G. Remark 4. The converse of each of the statements in Theorem 10 need not be true. Example 1. Let G be a noncomplete connected graph of order n ≥ 3. Then γmce(G) = 2 if G is any of the following: (i) G = K2 +Kn, n ≥ 1; (ii) G is obtained from Kn by adding a pendant edge where n ≥ 2; or (iii) G is the K2-gluing of K3 and Kn, n ≥ 3. 2.1. Nordhauss-Gaddum Type Results Remark 5. Following a similar proof, the statement in Corollary 1 remains true if γce(G) is changed to γce(G)+ or γmce(G). Let Ξ be an infinite collection of all connected graph G such that G is also connected. Theorem 11. For all G ∈ Ξ of order n ≥ 4, (i) 4 ≤ γ+ce(G) + γ+ce(G) ≤ 2n− 4; and (ii) 4 ≤ γ+ce(G)γ+ce(G) ≤ n2 − 4n+ 4. In particular, γ+ce(G) + γ+ce(G) = 4 if and only if n = 4, and γ+ce(G)γ+ce(G) = 4 if and only if n = 4. Proof. Let G ∈ Ξ be of order n ≥ 4. By Theorem 8 and Remark 5, γ+ce(G) 6= n and γ+ce(G) 6= n− 1. Thus, Theorem 4 yield 4 ≤ γ+ce(G) + γ+ce(G) ≤ (n− 2) + (n− 2) = 2n− 4 and 4 = (2)(2) ≤ γ+ce(G)γ+ce(G) ≤ (n− 2)(n− 2) = n2 − 4n+ 4. Suppose that γ+ce(G) + γ+ce(G) = 4. Then, necessarily, γ+ce(G) = 2 and γce(G) = 2. By Theorem 9, n = 4. Conversely, if n = 4, then γ+ce(G)+γ+ce(G) = 4 Similarly, γ+ce(G)γ+ce(G) = 4 if and only if n = 4. Corollary 7. If G ∈ Ξ of order n ≥ 4, then (i) γ+ce(G) + γ+ce(G) = 4 if and only if G = P4, H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 546 (ii) γ+ce(G)γ+ce(G) = 4 if and only if G = P4. Proof. The result follows from Theorem 11 and Corollary 6. Theorem 11 and Theorem 9 imply that if G ∈ Ξ is of order n ≥ 5, then 6 ≤ γ+ce(G) + γ+ce(G) ≤ 2n− 4 (1) and 9 ≤ γ+ce(G)γ+ce(G) ≤ n2 − 4n+ 4. (2) Since γ+ce(C5) = γ+ce(C5) = 3, bounds in Equations 1 and 2 are sharp. Following the proof of Theorem 11, the following is true. Theorem 12. For all G ∈ Ξ of order n ≥ 4, (i) 4 ≤ γmce(G) + γmce(G) ≤ 2n− 4; and (ii) 4 ≤ γmce(G)γmce(G) ≤ n2 − 4n+ 4. Proof. Let G ∈ Ξ be of order n ≥ 4. Note that whenever G is Kn or K1,n−1, G is disconnected. Thus, Theorem 8 and Corollary 4 imply that γmce(G) + γmce(G) ≤ (n− 2) + (n− 2) = 2n− 4 and γmce(G)γmce(G) ≤ (n− 2)(n− 2) = n2 − 4n+ 4. The left inequalities follow from Theorem 4. Remark 6. The bounds given in Theorem 12 are sharp. To see this, consider the graph G = P4. Observe that γmce(P4) = 2 = γmce(P4). 2.2. Realization Problem Theorem 13. For every positive integers a, b, c with 1 ≤ a ≤ b ≤ c there exists a connected graph G such that γce(G) = a, γmce(G) = b and γ+ce(G) = c. Proof. Suppose that a = b = c. Write V (K1,a−1) = {x, u1, u2, . . . , ua−1} as in Figure 1. Obtain G from K1,a−1 by adding pendant edges vjuj , j = 1, 2, . . . , a− 1 and then adding new edges va−1wa−1 and wa−1x as shown in Figure 1. Write D = {ua−1, va−1, wa−1, x}. Observe that for any s, t ∈ D, the sets {v1, v2, v3 . . . , va−2, s, t}, {u1, u2, . . . , ua−2, p, r} where p, r ∈ D \ {x} and sets of the form {uj , vk : j 6= k, j, k = 1, 2, . . . , a − 2} ∪ {s, t} are the only cost effective dominating sets in G. Therefore, γce(G) = a, γmce(G) = b and γ+ce(G) = c. H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 547 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . u1 u2 u3u4 ua−1 x K1,a−1 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ............................................................................ ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... ..................... ........................ ............................... ....................................................................................................... u1 x v1 u2 v2 u3 v3 u4 v4 ua−1va−1 wa−1 Figure 1: G obtained from K1,a−1 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava ............ .............. ...................... ....................................................................................G1 : Figure 2: G1 obtained from K1,a Suppose that a = b and c = b + 1. Obtain the graph G = G1 from K1,a by adding pendant edges ujvj , j = 1, 2, . . . , a and an edge xva as shown in Figure 2. Observe that the sets {u1, u2, . . . , ua}, {v1, v2, . . . , va}, {x, v1, v2, . . . , va−1} and sets {vj , uk : j 6= k, j, k = 1, 2, . . . , a} are the only minimal cost effective dominating sets in G. Thus, γmce(G) = a = b. Also, note that the set {x, v1, v2, . . . , va} is a γ+ce-set in G. Therefore γ+ce(G) = a+ 1 = b+ 1 = c. Suppose that a = b and c = b+ k for k ≥ 2. Let V (K2k) = {w1, w2, . . . , w2k}. Obtain G = G2 from G1 by joining complete graph K2k to exactly one of the end vertices of G1, say v1, as shown in Figure 3. .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava ............ .............. ...................... .................................................................................... G1 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava ............ .............. ...................... .................................................................................... G2 .................................... .................................... .................................... .................................... .................................... ................................................................................................ ............................................................................ ................ ............... ............... ............... ............... ........ ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ......... ........ ........ ..... ......... ...... ......... . ......... ........ ........ ..... ......... ........ ........ ..... ......................................................................... ...................................................................................................................... ........................................................................................................................................................................ ...................................................................................................................... .................................................................................................................................................................... ..................................................................................................................................................................................................................... .................................................................................................. ... w1 w2 w2k−2 w2k−1 w2k Figure 3: G2 obtained from K1 Observe that for each r ∈ {ua, va}, the set {r, u2, u3, . . . , ua−1, v1} is a γce-set in H. Nuenay-Maglanque, F.Jamil / Eur. J. Pure Appl. Math, 14 (2) (2021), 537-550 548 G. Thus, γce(G) = 1 + a − 1 = a. Also, γmce(G) = b which is determined by the set {x, v2, v3, . . . , va−1, z} where z ∈ V (K2k+v1). Moreover, note that the set {x, v2, v3, . . . , va, w1, w2, . . . , wk−1, wk} is a γ+ce-set in G. Therefore, γ+ce(G) = 1+a−1+k = a+k = b+k = c. Suppose that b = a + 1 and c = b. Obtain G = G3 is from K1,a by adding pendant edges ujvj , j = 1, 2, . . . , a as shown in Figure 4. Then γce(G) = a which is determined by .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . u1 u2 u3u4 ua x K1,a .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava G3 Figure 4: G3 obtained from K1,a the set {u1, u2, . . . , ua}. Also, γmce(G) = a+ 1 = b and γ+ce(G) = c which are determined by the set {v1, v2, . . . , va, x}. Suppose that c = b + k, k ≥ 2. Obtain G by joining the complete graph K2k to exactly one of end vertices of G3 say in v1 , as shown in Figure 5. .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava G3 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 uava G4 .................................... .................................... .................................... .................................... .................................... ................................................................................................ ............................................................................ ................ ............... ............... ............... ............... ........ ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ......... ........ ........ ..... ......... ...... ......... . ......... ........ ........ ..... ......... ........ ........ ..... ......................................................................... ...................................................................................................................... ........................................................................................................................................................................ ...................................................................................................................... .................................................................................................................................................................... ..................................................................................................................................................................................................................... .................................................................................................. ... w1 w2 w2k−2 w2k−1 w2k Figure 5: G4 obtained from G3 Now, γce(G) = a which is determined by the set {u2, u3, . . . , ua, v1}. Note that γmce(K2k) = 1. Thus, γmce(G) = a + 1 = b which is determined by the set {x, v2, v3, . . . , va, z} z ∈ V (K2k+v1). Also, observe that the set {w1, w2, . . . , wk} is a γ+ce-set in K2k. Thus, {x, v1, v2, . . . , va, w1, . . . , wk} is a γ+ce-set in G. Therefore, γ+ce(G) = 1 + a+ k = b+ k = c. Suppose that b = a+k and c = b. Obtain G = G5 from G3 by adding k pendant edges vahj , j = 1, 2, . . . , k as shown in Figure 6. Then γce(G) = a which is determined by the REFERENCES 549 .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 ua va G5 .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ ................................................ .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ............ ........... ........... ........... ........... ........... . ................. ................ ............... ........................................ ... h1 h2 h3 h4 h5 hk Figure 6: G5 obtained from G3 set {u1, u2, . . . , ua−1, ua}. Also, observe that the set {v1, v2, . . . , va−1, x, h1, h2, . . . , hk} is a γmce-set in G and is the only cost effective dominating set in G which is of maximum order. Thus, γmce(G) = a − 1 + 1 + k = a + k = b = c = γ+ce(G). Now, suppose that c = b+ t, t ≥ 1. Obtain G = G6 from G5 by joining complete graph K2t to exactly one of the end vertices of G4, say v1, as shown in Figure 7. .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 ua va G5 .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ ................................................ .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ............ ........... ........... ........... ........... ........... . ................. ................ ............... ........................................ ... h1 h2 h3 h4 h5 hk .................................... .................................... .................................... .................................... ........................................................................ ....................................................................................................................................... ....... .. ........ ........ ........ ........ ........ ........ ........ .. .......... ......... ......... ......... ......... ......... ......... ......... ................................................................................... . . . .................................... ........................................................................ .................................... .................................... ........................................ ........................................ ......... ........ ........ ........ ....... ............................................. ......... ......... ..... u1 x v1 u2 v2 u3 v3 u4 v4 ua va G6 .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ ................................................ .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ............ ........... ........... ........... ........... ........... . ................. ................ ............... ........................................ ... h1 h2 h3 h4 h5 hk .................................... .................................... .................................... .................................... .................................... ................................................................................................ ............................................................................ ................ ............... ............... ............... ............... ........ ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ......... ........ ........ ..... ......... ...... ......... . ......... ........ ........ ..... ......... ........ ........ ..... ......................................................................... ...................................................................................................................... ........................................................................................................................................................................ ...................................................................................................................... .................................................................................................................................................................... ..................................................................................................................................................................................................................... .................................................................................................. ... w1 w2 w2t−2 w2t−1 w2t Figure 7: G6 obtained from G5 Then the set {u2, u3, . . . , ua−1, v1, va} is a γce-set in G. Thus, γce(G) = a − 2 + 2 = a. Also, since γmce(K2t + v1) = 1, γmce(G) = a + k = b which is determined by the set {v1, v2, . . . , va−1, x, h1, . . . , hk}. Also, observe that since the set {v1, v2, . . . , va−1, x, h1, . . . , hk, w1, . . . , wt} is a γ+ce-set in G, γ+ce(G) = a−1+1+k+t = a+k+t = b+k = c. References [1] R. Aharoni, E.C. Milner, K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory, Ser. B 50 (1) (1990) 1−10. [2] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, T.L. McCoy, I. Vasylieva, Cost effective domination in graphs, Cong. Numer. 211 (2012) 197−209. REFERENCES 550 [3] Bostjan Bresar Vizing-like conjecture for the upper domination of Cartesian products of graphs -the proof The Electronic Journal of Combinatorics 12 (2005) [4] F. Buckley, F. Harary. Distance in Graphs. Redwood City. CA: Addison-Wesley. [5] 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. [6] S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, Very Cost effective bipartitions in graphs. AKCE International Journal of Graphs and Combinatorics. 12(2015)155-160. [7] F. Jamil and H. Maglanque On cost effective domination in join, corona and compo- sition of graphs, European Journal of Pure and Applied Mathematics ,Graph theory. Vol.12, No.3, pp. 978-998, 2019. [8] H. Nuenay and F. Jamil On the minimal geodetic domination in graphs, Discussiones Mathematicae,Graph theory. Vol.45, pp. 403-418, 2015.