EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 14, No. 4, 2021, 1324-1336
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

On k-Cost Effective Domination Number in the Join of
Graphs

Jesrael B. Palco1,∗, Rolando N. Paluga2, Gina A. Malacas3

1 Department of Physical Sciences and Mathematics, College of Science and Environment,
Mindanao State University at Naawan, 9023, Naawan, Misamis Oriental, Philippines
2 Department of Mathematics, College of Mathematics and Natural Sciences,
Caraga State University , 8600, Ampayon, Butuan City, Philippines
3 Department of Mathematics and Statistics, College of Science and Mathematics,
Mindanao State University-Iligan Institute of Technology, 9200, Iligan City, Philippines

Abstract. In this paper, we characterized the k-cost effective domination in the join of graphs.
Further, we investigate the k-cost effective domination, cost effective domination index, maximal
cost effective domination in the join of graphs.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: k-cost effective set, k-cost effective domination index, maximal cost
effective domination.

1. Introduction

Let G = (V (G), E(G)) be a connected simple graph and v ∈ V (G). The neighborhood
of v in the set NG(v) = N(v) = {u ∈ V (G) : uv ∈ E(G)}. The degree of a vertex v in
a graph G, denoted by degG(v), is |N(v)|. A subset S of V (G) is a dominating set of
G if for every v ∈ V (G) \ S, there exists u ∈ S such that uv ∈ E(G). The domination
number γ(G) of G is the minimum cardinality of a dominating set of G. A subset S of
V (G) is an independent set of 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.

Let k ≥ 0 be an integer. Consider a vertex v, its neighborhood set, N(v) and
the vertex-set of G, V (G). A vertex v ∈ S ⊆ V (G) is said to be k-cost effective if
|N(v) ∩ (V (G) \ S)| ≥ |N(v) ∩ S| + k. A dominating set S is k-cost effective, if every
vertex in S is k-cost effective. The minimum cardinality of a k-cost effective dominating

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i4.4117

Email addresses: jesrael.palco@msunaawan.edu.ph (J. B. Palco),
rnpaluga@carsu.edu.ph (R. N. Paluga), gina.malacas@g.msuiit.edu.ph (G. A. Malacas)

http://www.ejpam.com 1324 © 2021 EJPAM All rights reserved.



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1325

set of G is the k-cost effective domination number γkce(G) of G. In cases where there is
no k-cost effective dominating set for G, the k-cost effective domination number of G is
infinity. The k-cost effective domination index of G, denoted by η(G), is the maximum
value of k such that k-cost effective domination number is finite. That is,

η(G) = max{k : γkce(G) is finite.}

The maximal cost effective domination number of G is equal to γ
η(G)
ce (G).

2. Results

Theorem 1. Let G and H be connected graphs, k ≥ max{|V (G)|, |V (H)|}, and
S ⊆ V (G + H). Then S is a k-cost effective dominating set in G + H if and only if
one of the following holds:

(i) S is (k − |V (H)|)-cost effective dominating set in G;

(ii) S is (k − |V (G)|)-cost effective dominating set in H;

(iii) V (G) ∩ S is (k − k1)-cost effective dominating set in G, where
k1 = |V (H)| − 2|V (H) ∩ S| and V (H) ∩ S is (k − k2)-cost effective dominating
set in H, where k2 = |V (G)| − 2|V (G) ∩ S|.

Proof: Let k ≥ max{|V (G)|, |V (H)|}, and S ⊆ V (G + H). Suppose S is a k-cost
effective dominating set in G+H and let x ∈ S. Then

|NG+H(x) \ S| − |NG+H(x) ∩ S| ≥ k.

Suppose S ⊆ V (G). Then S is a dominating set in G. Now,

|NG+H(x) \ S| − |NG+H(x) ∩ S| = |V (H)|+ |NG(x) \ S|
− |NG(x) ∩ S|

≥ k.

This implies that,
|NG(x) \ S| − |NG(x) ∩ S| ≥ k − |V (H)|.

Hence, S is (k − |V (H)|)-cost effective dominating set in G. Similarly, if S ⊆ V (H), then
S is (k − |V (G)|)-cost effective dominating set in H.

Suppose that S1 = V (G)∩S ̸= ∅ and S2 = V (H)∩S ̸= ∅. Since S is a k-cost effective
dominating set in G+H,

|NG+H(x) \ S| − |NG+H(x) ∩ S| ≥ k.

Let x ∈ S1 ⊆ S. Then

|NG+H(x) \ S| − |NG+H(x) ∩ S| = |NG(x) \ S1|+ |V (H) \ S2| − |NG(x) ∩ S1| − |S2|



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1326

= |NG(x) \ S1|+ |V (H)| − |S2| − |NG(x) ∩ S1| − |S2|
= |NG(x) \ S1| − |NG(x) ∩ S1|+ |V (H)| − 2|S2|.

This implies that,

|NG(x) \ S1| − |NG(x) ∩ S1| ≥ k − |V (H)|+ 2|V (H) ∩ S|
= k − (|V (H)| − 2|V (H) ∩ S|)
= k − k1,

where k1 = |V (H)|−2|V (H)∩S|. Thus, S1 = V (G)∩S is (k−k1)-cost effective dominating
set in G. Similarly, S2 = V (H) ∩ S is (k − k2)-cost effective dominating set in H.

Conversely, suppose that S satisfies Property (i). Then S is a dominating set in G+H
and

|NG(x) \ S| − |NG(x) ∩ S| ≥ k − |V (H)|, ∀x ∈ S.

Now,

|NG+H(x) \ S| − |NG+H(x) ∩ S| = |V (H)|+ |NG(x) \ S|
− |NG(x) ∩ S|

≥ |V (H)|+ k − |V (H)|
= k,

for all x ∈ S. Since x is arbitrary, S is a k-cost effective dominating set in G+H. Similarly,
if S satisfies Property (ii), then S is a k-cost effective dominating set in G+H. Suppose
S satisfies Property (iii) and x ∈ V (G) ∩ S. Then

|NG(x) \ S| − |NG(x) ∩ S| ≥ k − k1,

where k1 = |V (H)| − 2|V (H) ∩ S|. Now,

|NG+H(x) \ S| − |NG+H(x) ∩ S| = |NG(x) \ S|+ |V (H) \ S| − |NG(x) ∩ S|+ |V (H) ∩ S|
= |NG(x) \ S| − |NG(x) ∩ S|+ |V (H) \ S| − |V (H) ∩ S|
= |NG(x) \ S| − |NG(x) ∩ S|+ |V (H)| − 2|V (H) ∩ S|
≥ k − k1 + k1

= k.

Similarly, for each x ∈ V (H) ∩ S, |NG+H(x) \ S| − |NG+H(x) ∩ S| ≥ k. Therefore, S is a
k-cost effective dominating set in G+H.

Corollary 1. Let G and H be connected graphs, k ≥ max{|V (G)|, |V (H)|}. If S is a
k-cost effective dominating set in G+H, then one of the following holds:

(i) S ⊆ V (G) and k ≤ η(G) + |V (H)| ;

(ii) S ⊆ V (H) and k ≤ η(H) + |V (G)|;



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1327

(iii) k ≤ min{η(G) + |V (H)| − 2|V (H) ∩ S|, η(H) + |V (G)| − 2|V (G) ∩ S|}.

Theorem 2. Let G and H be connected graphs such that γ(G) = 1 or γ(H) = 1 and
0 ≤ k ≤ |V (H)|+ |V (G)| − 1. Then S ⊆ V (G+H) is a γkce-set in G+H if and only if S
is a γ-set in G or S is a γ-set in H.

Corollary 2. Let G and H be connected graphs such that γ(G) = 1 or γ(H) = 1. Then

γkce(G+H) =

{
1, if 0 ≤ k ≤ |V (H)|+ |V (G)| − 1

∞, if k > |V (H)|+ |V (G)| − 1.

Corollary 3. Let G and H be connected graphs such that γ(G) = 1 or γ(H) = 1. Then

η(G+H) = |V (H)|+ |V (G)| − 1 and γ
η(G+H)
ce (G+H) = 1.

In the succeeding theorems, γ(G) ≥ 2 and γ(H) ≥ 2 and assume that
∆(G) + |V (H)| ≤ ∆(H) + |V (G)|.

Theorem 3. Let G and H be connected graphs such that min{γ(G), γ(H)} ≥ 2 and
0 ≤ k ≤ ∆(G) + |V (H)| − 2. Then S is a γkce-set in G+H if and only if |S| = 2 and one
of the following holds:

(i) |V (G) ∩ S| = 1 and |V (H) ∩ S| = 1;

(ii) S is a γ-set in G such that k − |V (H)|+ 2 ≤ δ(S : G);

(iii) S is a γ-set in H such that k − |V (G)|+ 2 ≤ δ(S : H).

Proof: Suppose that A = {a, b} such that degG(a) = ∆(G) and
degH(b) = ∆(H). Clearly, A is a dominating set in G+H. Moreover,

|NG+H(a) \A| − |NG+H(a) ∩A| = degG(a) + |V (H)|
= ∆(G) + |V (H)|
> ∆(G) + |V (H)| − 2

≥ k.

and

|NG+H(b) \A| − |NG+H(b) ∩A| = degH(b) + |V (G)|
= ∆(H) + |V (G)|
≥ ∆(G) + |V (H)|
> ∆(G) + |V (H)| − 2

≥ k.

Thus, A is a k-cost effective dominating set in G + H. Accordingly,
γkce(G + H) = |S| ≤ 2. Suppose that |S| = 1. Then γ(G) = 1 or γ(H) = 1, which is



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1328

a contradiction to that fact that min{γ(G), γ(H)} ≥ 2. Therefore, γkce(G+H) = 2. Since
S is a γkce-set in G+H, |S| = 2.

Clearly, |V (G) ∩ S| = 1 and |V (H) ∩ S| = 1. Thus, Property (i) holds.
Suppose that S ⊆ V (G). Since S is a dominating set in G+H, S is a dominating set

in G. Now, γ(G) ≥ 2, so S is a minimum dominating set in G, that is, S is a γ-set in G.
Let S = {a1, a2} ⊆ V (G). Suppose a1 and a2 are adjacent in S. Then

|NG+H(ai) \ S| − |NG+H(ai) ∩ S| = (|V (H)|+ degG(ai)− 1)− 1

= |V (H)|+ degG(ai)− 2

≥ |V (H)|+ δ(S : G)− 2

≥ k, i = 1, 2.

Thus, k − |V (H)|+ 2 ≤ δ(S : G). Suppose a1 and a2 are not adjacent in S. Then

|NG+H(ai) \ S| − |NG+H(ai) ∩ S| = |V (H)|+ degG(ai)

> |V (H)|+ degG(ai)− 2

≥ |V (H)|+ δ(S : G)− 2

= k, i = 1, 2.

Thus, k − |V (H)|+ 2 ≤ δ(S : G). Similarly, k − |V (G)|+ 2 ≤ δ(S : H).
Conversely, suppose that S satisfies Property (i). Then S is a γ-set in G+H. Moreover,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = |V (H)| − 1 + degG(a)− 1

= |V (H)|+∆(G)− 2

≥ k.

and

|NG+H(b) \ S| − |NG+H(b) ∩ S| = |V (G)| − 1 + degH(b)− 1

= |V (G)|+∆(H)− 2

= |V (H)|+∆(G)− 2

≥ k.

Thus, S is a k-cost effective dominating set in G + H. Hence, S is a γkce-set in G + H.
Suppose that S satisfies Property (ii). Then S is a γ-set in G + H. Suppose a1 and a2
are adjacent in S. Then

|NG+H(ai) \ S| − |NG+H(ai) ∩ S| = (|V (H)|+ degG(ai)− 1)− 1

= |V (H)|+ degG(ai)− 2

≥ |V (H)|+ δ(S : G)− 2

≥ k.



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1329

Suppose a1 and a2 are not adjacent in S. Then

|NG+H(ai) \ S| − |NG+H(ai) ∩ S| = |V (H)|+ degG(ai)

> |V (H)|+ degG(ai)− 2

≥ |V (H)|+ δ(S : G)− 2

= k.

Thus, S is a k-cost effective dominating set in G + H. Suppose that a singleton set is
a dominating set in G + H. Then γ(G) = 1 or γ(H) = 1, which a contradiction to the
fact that min{γ(G), γ(H)} ≥ 2. Hence, S is a γkce-set in G +H. Similarly, if S satisfies
Property (iii), then S is a γkce-set in G+H.

Therefore, S is a γkce-set in G+H.

Theorem 4. Let G and H be connected graphs such that min{γ(G), γ(H)} ≥ 2
and k = ∆(G) + |V (H)| − 1. Then S is a k-cost effective dominating set in G+H if and
only if one of the following holds:

(i) S is an independent dominating set in G such that δ(S : G) ≥ ∆(G)− 1;

(ii) S is a dominating set in H such that 0 ≤ rH(a) + 2|NH(a) ∩ S| − t ≤ 1, where
rH(a) = ∆(H) − degH(a) and t = ∆(H) + |V (G)| − ∆(G) − |V (H)|, and
degH(a) + |V (G)| − 2|NH(a) ∩ S| = ∆(G) + |V (H)| − 1.

Proof: Suppose that S is a k-cost effective dominating set in G + H. Consider the
following cases:
Case 1: V (G) ∩ S ̸= ∅ and V (H) ∩ S ̸= ∅.

Let a ∈ V (G) ∩ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)| − 1

= k,

a contradiction. Thus, this case is not possible.
Case 2: S ⊆ V (G).

Suppose S is not an independent dominating set G. Let a ∈ S. Then there exists
a
′ ∈ S such that dG(a, a

′
) = 1. Now

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)| − 1

= k,

a contradiction. Thus, in this case S is an independent dominating set in G. Let
rG(a) = ∆(H)− degG(a). Now, S is a k-cost effective dominating set in G+H, so

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1330

= ∆(G)− rG(a) + |V (H)|
≥ ∆(G) + |V (H)| − 1.

Thus, rG(a) ≤ 1 and degG(a) ≥ ∆(G)− 1 for all a ∈ S. Hence, δ(S : G) ≥ ∆(G)− 1.
Case 3: S ⊆ V (H).

Since S is a k-cost effective dominating set in G+H, S is a dominating set in H. Let
a ∈ S and rH(a) = ∆(H)− degH(a), and t = ∆(H) + |V (G)| −∆(G)− |V (H)| . Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t).

Thus, 0 ≤ rH(a) + 2|NH(a) ∩ S| − t ≤ 1. Hence, degH(a) + |V (G)| − 2|NH(a) ∩ S| =
∆(G) + |V (H)| − 1 .

Conversely, suppose that S satisfies Property (i). Then S is a dominating set in G+H.
Let a ∈ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|
= ∆(G)− 1 + |V (H)|
= k.

Hence, S is a k-cost effective dominating set in G+H.
Suppose that S satisfies Property (ii). Then S is a dominating set in G+H. Now,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t).

If rH(a) + 2|NH(a) ∩ S| − t = 0, then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t

= ∆(G) + |V (H)|
> ∆(G) + |V (H)| − 1

= k.

Hence, S is a k-cost effective dominating set in G+H. If

rH(a) + 2|NH(a) ∩ S| − t = 1



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1331

then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t

= ∆(G) + |V (H)| − 1

= k.

Hence, S is a k-cost effective dominating set in G+H.
Therefore, S is a k-cost effective dominating set in G+H.

Theorem 5. Let G and H be connected graphs such that
min{γ(G), γ(H)} ≥ 2 and k = ∆(G) + |V (H)|. Then S is a k-cost effective dominating
set in G+H if and only if one of the following holds:

(i) S is an independent dominating set in G such that δ(S : G) = ∆(G);

(ii) S is a dominating set inH such that degH(a)+|V (G)| = 2|NH(a)∩S|+∆(G)+|V (H)|
and rH(a) + 2|NH(a) ∩ S| − t = 0, where rH(a) = ∆(H) − degH(a),
t = ∆(H) + |V (G)| −∆(G)− |V (H)|.

Proof: Suppose that S is a k-cost effective dominating set in G + H. Consider the
following cases:
Case 1: V (G) ∩ S ̸= ∅ and V (H) ∩ S ̸= ∅.

Let a ∈ V (G) ∩ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)|
= k,

a contradiction. Thus, this case is not possible.
Case 2: S ⊆ V (G).

Suppose S is not an independent dominating set G. Let a ∈ S. Then there exists
a
′ ∈ S such that dG(a, a

′
) = 1. Now

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)|
= k,

a contradiction. Thus, in this case S is an independent dominating set in G. Now,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|
= ∆(G) + |V (H)|



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1332

= k,

Thus, degG(a) = ∆(G) ∀ a ∈ S. Hence, δ(S : G) = ∆(G).
Case 3: S ⊆ V (H).

Since S is a k-cost effective dominating set in G+H, S is a dominating set in H. Let
a ∈ S and rH(a) = ∆(H)− degH(a), and t = ∆(H) + |V (G)| −∆(G)− |V (H)|. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t).

Thus, rH(a) + 2|NH(a) ∩ S| − t = 0. Hence, degH(a) + |V (G)| = 2|NH(a) ∩ S|+∆(G) +
|V (H)|.

Conversely, suppose that S satisfies Property (i). Then S is a dominating set in G+H.
Let a ∈ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|
= δ(S : G) + |V (H)|
= ∆(G) + |V (H)|
= k.

Hence, S is a k-cost effective dominating set in G+H.
Suppose that S satisfies Property (ii). Then S is a dominating set in G+H. Now,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)|+∆(H) + |V (G)| −∆(G)

− |V (H)| −∆(H) + degH(a)− 2|NH(a) ∩ S|
= |V (G)|+ degH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)|
= k.

Thus, S is a k-cost effective dominating set in G+H.
Therefore, S is a k-cost effective dominating set in G+H.

Theorem 6. Let G and H be connected graphs such that min{γ(G), γ(H)} ≥ 2 and
∆(G) + |V (H)|+ 1 ≤ k ≤ ∆(H) + |V (G)|. Then S is a k-cost effective dominating set in
G+H if and only if S is a dominating set in H such that t− rH(a)− 2|NH(a) ∩ S| ≥ p,
where 1 ≤ p ≤ t and t = ∆(H) + |V (G)| −∆(G)− |V (H)|, and rH(a) = ∆(H)− degH(a)
and degH(a) + |V (G)| ≥ p+ 2|NH(a) ∩ S|+∆(G) + |V (H)|.



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1333

Proof: Suppose that S is a k-cost effective dominating set in G + H. Consider the
following cases:
Case 1: V (G) ∩ S ̸= ∅ and V (H) ∩ S ̸= ∅.

Let a ∈ V (G) ∩ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)|+ 1

≤ k,

a contradiction. Thus, in this case is not possible.
Case 2: S ⊆ V (G).

Suppose S is not an independent dominating set G. Let a ∈ S. Then there exists
a
′ ∈ S such that dG(a, a

′
) = 1. Now

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

< ∆(G) + |V (H)|+ 1

≤ k,

a contradiction. Thus, in this case S is an independent dominating set in G. Thus,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|
= ∆(G)− rG(a) + |V (H)|
≤ ∆(G) + |V (H)|+ 1

≥ k,

a contradiction. Thus, in this case is not possible.
Case 3: S ⊆ V (H).

Since S is a k-cost effective dominating set in G+H, S is a dominating set in H. Let
a ∈ S, rH(a) = ∆(H)−degH(a) and 1 ≤ p ≤ t, where t = ∆(H)+|V (G)|−∆(G)−|V (H)|.
Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|.

Thus, t−rH(a)−2|NH(a)∩S| ≥ p. Hence, degH(a)+ |V (G)| ≥ p+2|NH(a)∩S|+∆(G)+
|V (H)|.

Conversely, suppose that S is a dominating set in H such that
t− rH(a)− 2|NH(a) ∩ S| ≥ p, where 1 ≤ p ≤ t and t = ∆(H) + |V (G)| −∆(G)− |V (H)|,
and rH(a) = ∆(H)−degH(a) and degH(a)+ |V (G)| ≥ p+2|NH(a)∩S|+∆(G)+ |V (H)|.
Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|



J. B. Palco, R. N. Paluga, G. A. Malacas / Eur. J. Pure Appl. Math, 14 (4) (2021), 1324-1336 1334

= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|
= k.

Hence, S is a k-cost effective dominating set in G+H.

Theorem 7. Let G and H be connected graphs such that min{γ(G), γ(H)} ≥ 2 and
k ≥ ∆(H) + |V (G)|+ 1. Then γkce(G+H) = ∞.

Proof: Let k ≥ ∆(H) + |V (G)| + 1. Suppose that there exists a k-cost effective
dominating set S in G+H. Consider the following cases:
Case 1: V (G) ∩ S ̸= ∅ and V (H) ∩ S ̸= ∅.

Let a ∈ V (H) ∩ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(H)− 1 + |V (G)| − 1

< ∆(H) + |V (G)|+ 1

= k,

a contradiction.
Case 2: S ⊆ V (G).

Suppose S is not an independent dominating set G. Let a ∈ S. Then there exists
a
′ ∈ S such that dG(a, a

′
) = 1. Now

|NG+H(a) \ S| − |NG+H(a) ∩ S| ≤ ∆(G)− 1 + |V (H)| − 1

≤ ∆(H)− 1 + |V (G)| − 1

< ∆(H) + |V (G)|+ 1

= k,

a contradiction. Thus, in this case S is an independent dominating set in G. Thus,

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degG(a) + |V (H)|
= ∆(G)− rG(a) + |V (H)|
= ∆(H)− rG(a) + |V (G)|
< ∆(H) + |V (G)|+ 1

= k,

a contradiction.
Case 3: S ⊆ V (H). . Let a ∈ S. Then

|NG+H(a) \ S| − |NG+H(a) ∩ S| = degH(a)− |NH(a) ∩ S|+ |V (G)| − |NH(a) ∩ S|
= ∆(H)− rH(a)− 2|NH(a) ∩ S|+ |V (G)|
= ∆(G) + |V (H)|+ t− rH(a)− 2|NH(a) ∩ S|
= ∆(G) + |V (H)| − (rH(a) + 2|NH(a) ∩ S| − t)



REFERENCES 1335

= ∆(H) + |V (G)| − (rH(a) + 2|NH(a) ∩ S| − t)

< ∆(H) + |V (G)|+ 1

= k,

a contradiction. Hence, γkce(G+H) = ∞.
The next result follows from Theorem 3, Theorem 4, Theorem 5, Theorem 6 and

Theorem 7.

Corollary 4. Let G and H be connected graphs such that γ(G) ≥ 2, γ(H) ≥ 2 and
|V (H)|+∆(G) ≤ |V (G)|+∆(H). Then

γkce(G+H) =


2, if 0 ≤ k ≤ |V (G)|+∆(H)− 2

min{γ∗
i (G), γ∗(H)}, if |V (G)|+∆(H)− 1 ≤ k ≤ ∆(G) + |V (H)|

γ(H), if |V (H)|+∆(G) + 1 ≤ k ≤ |V (G)|+∆(H)

∞ if k ≥ |V (G)|+∆(H) + 1

,

where
γ∗i (G) = min{|S| : S is a γi-set in G and δ(S : G) ≥ ∆(G)− 1},
γ∗(H) = min{|S| : S is a γ-set in G and 0 ≤ ∆(G) + |V (H)| − |V (G)| − degH(a) +
2|NH(a) ∩ S| ≤ 1}, and
γ(H) = min{|S| : S is a γ-set in G and degH(a) + |V (G)| − |V (H)| − 2|NH(a)∩ S| ≥ p}

Corollary 5. Let G and H be connected graphs such that γ(G) ≥ 2, γ(H) ≥ 2 and
|V (H)| + ∆(G) ≤ |V (G)| + ∆(H). Then η(G + H) = |V (G)| + ∆(H) and

γ
η(G+H)
ce (G+H) = γ(H).

Acknowledgements

The authors thank the peer reviewers of the paper and readers of European Journal
of Pure and Applied Mathematics, for making the journal successful.

References

[1] M. Chellali, T. W. Haynes and S. T. Hedetniemi, Client–server and cost effective
sets in graphs, AKCE International Journal of Graphs and Combinatorics 15(2017),
211-2018.

[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.

[3] 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.

[4] 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, 978-998, 2019.



REFERENCES 1336

[5] J. Palco, R. Paluga and G. Malacas, On k-cost effective domination number, cost
effective domination index and maximal cost effective domination number of simple
graphs, Far East Journal of Mathematical Sciences (FJMS), Volume 114, Issue 1,
55-68, 2019.