EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 13, No. 3, 2020, 701-709
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

Upper Distance k- Cost Effective Numbers in the Join
of Graphs

Julius G. Caadan1,∗, Rolando N. Paluga2, Imelda S. Aniversario3

1 Surigao State College of Technology, 8400 Surigao City, Philippines
2 Department of Mathematics, College of Mathematics and Natural Sciences,
Caraga State University , 8600, Ampayon, Butuan City 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. Let k be a positive integer and G be a connected graph. The open k-neighborhood
set Nk

G(v) of v ∈ V (G) is the set Nk
G(v) = {u ∈ V (G) \ {v} : dG(u, v) ≤ k}. A set S of vertices of

G is a distance k- cost effective if for every vertex u in S, |Nk
G(u) ∩ Sc| − |Nk

G(u) ∩ S| ≥ 0. The
maximum cardinality of a distance k- cost effective set of G is called the upper distance k- cost
effective number of G. In this paper, we characterized a distance k- cost effective set in the join of
two graphs. As direct consequences, the bounds or the exact values of the upper distance k- cost
effective numbers are determined.

2020 Mathematics Subject Classifications: 05C12

Key Words and Phrases: Distance k-cost effective set, upper distance k-cost effective number,
join, t-fringe set, t- increment

1. Introduction

We assume that all graphs G = (V (G), E(G)) considered throughout this paper are
finite, simple, and undirected connected graphs. The basic graph theoretic concepts are
adapted from [1] and [7]. The notations V (G) and E(G) are the vertex set and edge set,
respectively, of G. The |V (G)| denotes the order of G and for any set S ⊆ V (G), |S| is
the cardinality of S.

Let G be a connected graph and v ∈ V (G). The open neighborhood of v in G,
denoted by NG(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 the cardinality of NG(v). The minimum degree of
G is δ(G) = min{degG(v) : v ∈ V (G)} and the maximum degree of G is ∆(G) =
max{degG(v) : v ∈ V (G)}. The distance between vertices u and v in G, denoted by

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v13i3.3657

Email addresses: juliusgcaadan@gmail.com (J. G. Caadan),
rnpaluga@carsu.edu.ph (R. N. Paluga), imelda.aniversario@g.msuiit.edu.ph (I. S. Aniversario)

https://www.ejpam.com 701 c© 2020 EJPAM All rights reserved.



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 702

dG(u, v), is the length of the shortest path from vertex u to vertex v in G. Thediameter
of G, denoted by diam(G), is the maximum distance between any two vertices in G.

For any positive integer k and v ∈ V (G), the open k- neighborhood set Nk
G(v) of

vertex v is the set of all vertices u of G such that 0 < dG(u, v) ≤ k. That is, Nk
G(v) =

{u ∈ V (G) : 0 < dG(u, v) ≤ k}. The degree of v in G of distance k , denoted by
degkG(v), is the cardinality of Nk

G(v). The minimum degree δk(G) of G with distance k
is δk(G) =min{degkG(v) : v ∈ V (G)} and the maximum degree of G with distance k is
∆k(G) =max{degkG(v); v ∈ V (G)}. Note that deg1

G(v) =degG(v), δ1(G) = δ(G), and
∆1(G) = ∆(G). A simple graph G is called regular if all vertices of G have the same
degree. Thus, ∆(G) = δ(G).

Given graphs G and H with disjoint vertex sets, the join of G and H, denoted by
G+H, is the graph with vertex set V (G+H) = V (G)∪ V (H) and edge set E(G+H) =
E(G)∪E(H)∪{uv : u ∈ V (G), v ∈ V (H)}. For a nonempty set S ⊆ V (G), the subgraph
〈S〉G of G induced by S is the maximal subgraph of G with vertices in S. The δ(G : S) =
min {degG(v) : v ∈ S}.

A vertex v in a set S ⊆ V (G) is a cost effective if |NG(v)∩Sc| − |NG(v)∩S| ≥ 0. A
set S ⊆ V (G) is called cost effective if every vertex v ∈ S is cost effective. The concept
of cost effective set in graph was introduced by Haynes, et.al. in [5] which was motivated
by Aharoni, et. al. in [8]. In 2018, Chellali, et. al. in [2] established a generalization
of this concept. Its application in computer networks plays a vital role: in particular in
maintaining edges in a network that are directly associated with the cost that should be
used effectively and in a set of servers (vertices) that each server is serving a maximal
number of clients (non-servers). We refer the readers to [2, 4] for some of its relevant
applications and to [3, 6, 9] for some investigations of the concepts.

In this paper, we characterized the distance k- cost effective sets in the join of two
graphs. As direct consequences, we determined the bounds or the exact values of the
upper distance k-cost effective numbers of the join of graphs.

2. Results

Remark 1. Let G be a connected graph. If S ⊆ V (G) is a distance k- cost effective then
every subset of S is also a distance k-cost effective in G.

Definition 1. Let G be a connected graph and k be a positive integer. A set S ⊆ V (G) is
a distance k- cost effective set of G if for every v ∈ S, |Nk

G(v) ∩ Sc| − |Nk
G(v) ∩ S| ≥ 0.

The upper distance k- cost effective number of a graph G, denoted by αkce(G), is the
maximum cardinality of a distance k - cost effective set in G.

It is worth noting that the concept of a distance 1- cost effective set in G is just
equivalent to the concept of a cost effective set in G.

Example 1. Let k and n be positive integers. For any complete graph Kn, a set S is a
distance k- cost effective in Kn if and only if |S| ≤ bn+1

2 c. Hence, αkce(Kn) = bn+1
2 c.

Remark 2. Let G and H be any connected graphs and k be any positive integer.



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 703

(i) If S ⊆ V (G) is a distance k- cost effective set in G, then S is a distance k-cost
effective set in G+H.

(ii) If S ⊆ V (H) is a distance k- cost effective set in H, then S is a distance k- cost
effective set in G+H.

Remark 3. Let G and H be any connected graphs and k be any positive integer. Then

αkce(G+H) ≥ max{αkce(G), αkce(H)}.

Example 2. Let G = C8 and H = K1,9. Then α1
ce(G + H) = α1

ce(H) and for any
connected graph G and for all integers k ≥ 2, αkce(G+K1) = αkce(G).

Theorem 1. Let k be a positive integer and G be a connected graph such that k ≥
diam(G). Then S is a distance k-cost effective set in G if and only if |S| ≤ b |V (G)|+1

2 c.

Proof: Let k be a positive integer and G be a connected graph such that k ≥ diam(G).
Suppose S is a distance k-cost effective set in G. Then for each u ∈ S,

|Nk
G(u) ∩ Sc| − |Nk

G(u) ∩ S| = |
(
V (G) \ {u}

)
∩ Sc| − |

(
V (G) \ {u}

)
∩ S|

= |Sc| −
(
|S| − 1

)
= |V (G)| − |S| − |S|+ 1

= |V (G)|+ 1− 2|S|
≥ 0.

That is, |S| ≤ |V (G)|+1
2 . Since |S| is an integer, |S| ≤ b |V (G)|+1

2 c.
Suppose that |S| ≤ b |V (G)|+1

2 c. Then |S| ≤ |V (G)|+1
2 . Equivalently, 2|S| ≤ |V (G)|+ 1.

Let u ∈ S. Then

|Nk
G(u) ∩ Sc| − |Nk

G(u) ∩ S| = |V (G)| − |S| − |S|+ 1

= |V (G)|+ 1− 2|S|
≥ |V (G)|+ 1−

[
|V (G)|+ 1

]
= 0.

Thus, S is a distance k-cost effective set in G.

Corollary 1. If k ≥ diam(G), then αkce(G) = b |V (G)|+1
2 c.

Corollary 2. Let G and H be connected graphs and an integer k ≥ 2. Then S is a
distance k-cost effective set in G+H if and only if |S| ≤ b |V (G)|+|V (H)|+1

2 c. Consequently,

αkce(G+H) = b |V (G)|+|V (H)|+1
2 c.

Proof: Follows from Theorem 1 since k ≥ diam(G+H) = 2.

Remark 4. For all positive integer k ≥ 2, αkce(G+H) = α2
ce(G+H).



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 704

Definition 2. Let G be a connected graph and t be a nonnegative integer. A set S ⊆ V (G)
is a t- fringe subset of G if ∆(〈S〉G) ≤ t. The t- fringe number of G, denoted by τt(G),
is the maximum cardinality of a t- fringe subset of G.

Example 3. Consider the graph G as shown in Figure 1. Let S1 = {v3, v5, v6, v7} and
S2 = {v2, v4, v5, v7}. Then ∆(〈S1〉G) = 3 and ∆(〈S2〉G) = 0. Thus, S1 is t-fringe subset
of G if t ≥ 3 while S2 is a t-fringe subset of G if t ≥ 0.

v1

v2

v3

v4

v5

v6
v7

Figure 1: The Graph G with ∆(G) = 5

Theorem 2. Let G be a connected graph, S ⊆ V (G), and t ≥ b∆(G)
2 c. If S is a distance

1-cost effective set in G, then S is a t-fringe subset of V (G).

Proof: Let S ⊆ V (G) be a distance 1-cost effective set in G. Then for u ∈ S,

|N1
G(u) ∩ Sc| − |N1

G(u) ∩ S| = degG(u)− deg〈S〉G(u)− deg〈S〉G(u)

= degG(u)− 2deg〈S〉G(u)

≥ 0.

It follows that degG(u) − 2deg〈S〉G(u) ≥ 0. Hence, 2deg〈S〉G(u) ≤ degG(u). Since u is

arbitrary, 2∆(〈S〉G) ≤ ∆(G). Equivalently, ∆(〈S〉G) ≤ ∆(G)
2 . Hence, ∆(〈S〉G) ≤ b∆(G)

2 c ≤
t. Accordingly, S is a t-fringe subset of V (G).

Theorem 3. Let G be a connected graph and H be any graph of order n ≥ 2, S ⊆ V (G),

and t ≥ bn+∆(G)
2 c. If S is a distance 1-cost effective set in G + H, then S is a t-fringe

subset of V (G).

Proof: Let u ∈ S. Then

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u)− deg〈S〉G(u) + n− deg〈S〉G(u)

= degG(u) + n− 2deg〈S〉G(u)

Since S is a distance 1-cost effective set in G + H, degG(u) + n − 2deg〈S〉G(u) ≥ 0.
Hence, 2deg〈S〉G(u) ≤ degG(u) + n. It follows that 2deg〈S〉G(u) ≤ ∆(G) + n, ∀ u ∈ S.

Since u is arbitrary, 2∆(〈S〉G) ≤ ∆(G) + n. Equivalently, ∆(〈S〉G) ≤ ∆(G)+n
2 . Hence,

∆(〈S〉G) ≤ b∆(G)+n
2 c ≤ t. Accordingly, S is a t-fringe subset of V (G).



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 705

Corollary 3. Let G be a connected graph, H be any graph of order n ≥ 2 and t ≥
bn+∆(G)

2 c. Then α1
ce(G+H) ≤ τt(G).

Theorem 4. Let G be a connected graph and H be any graph of order n ≥ 2, S ⊆ V (G),

and t ≤ bn+δ(G)
2 c. If S is a t-fringe subset of V (G), then S is a distance 1-cost effective

set in G+H.

Proof: Since S is a t-fringe subset of V (G), then ∆(〈S〉G) ≤ t ≤ bn+δ(G)
2 c ≤ n+δ(G)

2 .
It follows that 2∆(〈S〉G) ≤ δ(G) + n. Let u ∈ S. Then

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u)− deg〈S〉G(u) + n− deg〈S〉G(u)

= degG(u) + n− 2deg〈S〉G(u)

≥ degG(u) + n− 2∆(〈S〉G)

≥ degG(u) + n− (n+ δ(G)

= degG(u)− δ(G)

≥ 0.

Thus, S is a distance 1-cost effective set in G+H.

Corollary 4. Let G be a connected graph, H be any graph of order n ≥ 2, and t ≤
bn+δ(G)

2 c. Then α1
ce(G+H) ≥ τt(G).

The next theorem is an immediate consequence of Theorems 3 and 4.

Theorem 5. LetG be any regular graph, H be any graph of order n ≥ 2 and t = bn+∆(G)
2 c.

Then α1
ce(G+H) = τt(G).

Definition 3. Let G be a connected graph, S ⊆ V (G) and t be any integer. The π(G : S)
is defined as π(G : S) = max{2deg〈S〉G(v)−degG(v) : v ∈ S} . A set S is t- increment
subset of G if π(G : S) ≤ t.

Example 4. Consider the graph G as shown in Figure 1. Let S1 = {v2, v4, v6, v7},
S2 = {v1, v2, v5, v6}, and S3 = {v2, v3, v5, v7}. Then

π(G : S1) = max{2deg〈S1〉G(u)− degG(u) : u ∈ S1} =− 1

π(G : S2) = max{2deg〈S2〉G(u)− degG(u) : u ∈ S2} = 0

π(G : S3) = max{2deg〈S3〉G(u)− degG(u) : u ∈ S3} = 1

Thus, S1 is −1-increment, S2 is 0-increment, and S3 is 1-increment subsets of V (G).

Remark 5. Let G be a connected graph. If S = V (G), then π(G : S) = ∆(G).

Definition 4. Let t be any integer. The t-increment number of G, denoted by ρt(G), is
the maximum cardinality of a t-increment.



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 706

Example 5. Consider the graph G as shown in Figure 1. Observe that the sets {v3, v5, v6},
{v1, v3, v5, v6}, {v1, v2, v3, v5, v7} and {v1, v2, v4, v5, v6, v7} are 2-increment subsets of G
while S4 = V (G) is not a 2-increment subset of G since π(G : S4) = 5. Thus, ρ2(G) = 6.

Remark 6. Let G be a connected graph and t1 ≤ t2. If S ⊆ V (G) is a t1- increment,
then S is a t2- increment. Hence, ρt1(G) ≤ ρt2(G).

Theorem 6. Let G and H be connected graphs of order m and n, respectively. Then S
is a distance 1-cost effective set in G+H if and only if any of the following holds:

(i) S ⊆ V (G) is n-increment of G.

(ii) S ⊆ V (H) is m-increment of H.

(iii) V (G)∩S is (n−2q)-increment and V (H)∩S is (m−2p)-increment, where |V (G)∩S| =
p and |V (H) ∩ S| = q.

Proof: Suppose S is a distance 1-cost effective set in G + H. Consider the following
cases:

Case 1: S ⊆ V (G)
Let u ∈ S. Then

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u)− deg〈S〉G(u) + n− deg〈S〉G(u)

= degG(u) + n− 2deg〈S〉G(u)

= n−
(
2deg〈S〉G(u)− degG(u)

)
≥ 0.

Thus, n −
(
2deg〈S〉G(u) − degG(u)

)
≥ 0, for each u ∈ S. Equivalently, for each u ∈ S,

2deg〈S〉G(u)− degG(u) ≤ n. Hence, π(G : S) ≤ n. Thus, (i) holds.

Case 2: S ⊆ V (H)
By similar argument to case 1, (ii) holds.

Case 3: V (G) ∩ S 6= ∅ and V (H) ∩ S 6= ∅
Let u ∈ V (G) ∩ S. Suppose |V (G) ∩ S| = p, where 1 ≤ p ≤ m. Then for each u ∈ S,

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u)− deg〈V (G)∩S〉(u) + n− q − deg〈V (G)∩S〉(u)− q
= degG(u)− 2deg〈V (G)∩S〉(u) + n− 2q.

Since S is a distance 1-cost effective, degG(u) − 2deg〈V (G)∩S〉(u) + n − 2q ≥ 0, ∀ u ∈ S.
Thus, 2deg〈V (G)∩S〉(u)−degG(u) ≤ n−2q. This implies that V (G)∩S is (n−2q)-increment
of G. Similarly, let u ∈ V (H) ∩ S. Then for each u ∈ S,

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = m− p+ degH(u)− deg〈V (H)∩S〉(u)− p− deg〈V (H)∩S〉(u)− q



J. G. Caadan, R. N. Paluga, I. S. Aniversario / Eur. J. Pure Appl. Math, 13 (3) (2020), 701-709 707

= m− 2p+ degH(u)− 2deg〈V (H)∩S〉(u)

≥ 0.

It follows that 2deg〈V (H)∩S〉(u) − degH(u) ≤ m − 2p. This implies that V (H) ∩ S is
(m− 2p)-increment of H. Thus, (iii) holds.

Conversely, if (i) holds then π(G : S) ≤ n. Let u ∈ S. Then

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u) + n− 2deg〈S〉G(u)

= n−
(
2deg〈S〉G(u)− degG(u)

)
= n− π(G : S)

≥ n− n
= 0.

Thus, S is a distance 1-cost effective set in G+H.
Suppose (ii) holds. Let u ∈ S. Then by similar argument, S is a distance 1-cost

effective set in G+H.
Suppose (iii) holds. Then π(G : V (G) ∩ S) ≤ n− 2q and π(H : V (H) ∩ S) ≤ m− 2p.

Let u ∈ V (G) ∩ S. Then for each u ∈ S,

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = degG(u)− 2deg〈V (G)∩S〉(u) + n− 2q

= n− 2q − (2deg〈V (G)∩S〉(u)− degG(u))

= n− 2q − π(G : V (G) ∩ S)

≥ n− 2q − (n− 2q)

= 0.

Thus, S is a distance 1-cost effective set in G+H.
Similarly, let u ∈ V (H) ∩ S. Then for each u ∈ S,

|N1
G+H(u) ∩ Sc| − |N1

G+H(u) ∩ S| = m− 2p+ degH(u)− 2deg〈V (H)∩S〉(u)

= m− 2p−
(
2deg〈V (H)∩S〉(u)− degH(u)

)
= m− 2p− π(H : V (H) ∩ S)

≥ m− 2p− (m− 2p)

= 0.

Thus, S is a distance 1-cost effective set in G+H.

Corollary 5. Let G be a connected graph, S ⊆ V (G) and n ≥ 2. Then S is a distance
1-cost effective set in G+Kn if and only if S is n-increment.

Corollary 6. Let G be a connected graph and n ≥ 2. A set S ⊆ V (Kn) is a distance

1-cost effective in G+Kn if and only if |S| ≤ b |V (G)|+n+1
2 c.



REFERENCES 708

Corollary 7. Let G be a graph, n ≥ 2 and S ⊆ (G + Kn) such that V (G) ∩ S 6= ∅ and
V (Kn) ∩ S 6= ∅. Then S is a distance 1-cost effective set in G + Kn if and only if the
following hold:

(i) |S| ≤ b |V (G)|+n+1
2 c; and

(ii) V (G) ∩ S is (n− 2p)-increment, where p = |V (Kn) ∩ S| and 1 ≤ p ≤ n.

Theorem 7. Let G and H be connected graphs of order m and n, respectively. Then

α1
ce(G+H) = max{ρn(G), ρm(H), ρn−2q(G) + ρm−2p(H), 1 ≤ p ≤ m, 1 ≤ q ≤ n}.

Proof: Let S be an upper distance 1-cost effective set in G+H. Suppose S ⊆ V (G).
Then by theorem 6(i), |S| = ρn(G). Suppose S ⊆ V (H). Then by Theorem 6(ii), |S| =
ρm(H). Suppose V (G) ∩ S 6= ∅ and V (H) ∩ S 6= ∅. Then by Theorem 6(iii), |S| =
ρn−2q(G) + ρm−2p(H). Therefore,

α1
ce(G+H) = max{ρn(G), ρm(H), ρn−2q(G) + ρm−2p(H), 1 ≤ p ≤ m, 1 ≤ q ≤ n}.

Corollary 8. Let G be a graph and n ≥ 2. Then

α1
ce(G+Kn) = max{b |V (G)|+n+1

2 c, ρn(G)}.

Acknowledgements

This research is funded by the Commission of Higher Education (CHED) and Mindanao
State University-Iligan Institute of Technology.

References

[1] F. Buckley and F. Harary. Distance in Graphs. Addison-Wesley, Redwood City, CA,
1990.

[2] T.W. Haynes, M. Chellali, and S.T. Hedetniem. Client-server and cost effective sets in
graphs. AKCE International Journal of Graphs and Combinatorics, 15:211–218, 2018.

[3] T.W. Haynes, I. Vasylieva, and S.T. Hedetniemi. Very cost effective bipartitions in
graphs. AKCE International Journal of Graphs and Combinatorics, 12:155–160, 2015.

[4] T.W. Hayness, M. Henning, and S.T. Hedetniemi. Domination in graphs applied to
electrical power networks. J. Discrete Math, 15(4), 2000.

[5] S.M. Hedetniemi, T.W. Haynes, S.T. Hedetniemi, T.L. McCoy, and I. Vasylieva. Cost
Effective Domination in Graphs. Congr. Numer., 211:197–209, 2012.



REFERENCES 709

[6] F. Jamil and H. Nuenay-Maglanque. Cost Effective Domination in the Join, Corona
and Composition of Graphs. European Journal of Pure and Applied Mathematics,
12(3):978–998, 2019.

[7] L. Lesniaks, G. Chartrand, and P. Zhang. Graphs and Digraphs (6th ed). Taylor and
Francis Group, LLC CRC Press, 2016.

[8] E.C. Milners, R.Aharoni, and K. Prikry. Unfriendly partitions of a graph. J. Combin.
Theory, Ser B 50(1):1–10, 1990.

[9] 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, 114(1):55–68, 2019.