EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 12, No. 4, 2019, 1779-1786
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

Forcing Subsets for γc-sets and γt-sets in the
Lexicographic Product of Graphs

Cris L. Armada1, Sergio R. Canoy, Jr.2,∗, Carmelito E. Go3

1 Mathematics Department, Cebu Normal University, 6000 Cebu City, Philippines
2 Department of Mathematics and Statistics, College of Sciences and Mathematics, Center for
Graph Theory, Algebra, and Analysis, Premier Research Institute in Science and Mathematics,
Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines
3 Department of Mathematics, College of Natural Sciences and Mathematics, Mindanao State
University - Main Campus, 9700 Marawi City, Philippines

Abstract. In this paper, the connected dominating sets and total dominating sets in the lex-
icographic product of two graphs are characterized. Further, the connected domination, total
domination, forcing connected domination and forcing total domination numbers of these graphs
are determined.
2010 Mathematics Subject Classifications: 05C69
Key Words and Phrases: Connected domination, total domination, forcing subset, lexicographic
product

1. Introduction

Let G = (V (G), E(G)) be a connected graph. A set D ⊆ V (G) is a dominating set of
G if every vertex in V (G)\D is adjacent to at least one vertex in D. A set S ⊆ V (G) is
a total dominating set (resp. connected dominating set) of G if each vertex in V (G) is
adjacent to some vertex in S (resp. S is a dominating set and the subgraph 〈S〉 induced
by S is connected in G). The total domination number γt(G) (resp. connected domination
number γc(G)) of G is the minimum cardinality of a total dominating set (resp. connected
dominating set). If S is a total dominating set (resp. connected dominating set) with
|S| = γt(G) (resp. |S| = γc(G) ), then we call S a minimum total dominating set (resp.
minimum connected dominating set) of G or a γt-set (resp. γc-set) in G.

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v12i4.3485

Email addresses: cris.armada@g.msuiit.edu.ph, invictuscris@yahoo.com (C. Armada),
serge_canoy@yahoo.com (S. Canoy)

http://www.ejpam.com 1779 c© 2019 EJPAM All rights reserved.



C. Armada, S. Canoy Jr., C. Go / Eur. J. Pure Appl. Math, 12 (4) (2019), 1779-1786 1780

Let T be a γt-set of a graph G. A subset S of T is said to be a forcing subset for T if
T is the unique γt-set containing S. The forcing total domination number of T is given by
fγt(T ) = min{|S| : S is a forcing subset for T}. The forcing total domination number of
G is given by

fγt(G) = min{fγt(T ) : T is a γt-set of G}.

Let C be a γc-set of a graph G. A subset D of C is said to be a forcing subset for C if C
is the unique γc-set containing D. The forcing connected domination number of C is given
by fγc(C) = min{|D| : D is a forcing subset for C}. The forcing connected domination
number of G is given by

fγc(G) = min{fγc(C) : C is a γc-set of G}.

Chartrand et. al [2] initiated the investigation on the relation between forcing and
domination concepts in 1997 and used the term "forcing domination number". In 2017,
John et. al [3] investigated the forcing connected domination of a graph. In 2018, Canoy et.
al [1] investigated the forcing domination number of graphs under some binary operations.

The lexicographic product (composition) G[H] of two graphs G and H is the graph with
V (G[H]) = V (G)× V (H), and (u, u′)(v, v′) ∈ E(G[H]) if and only if either uv ∈ E(G) or
u = v and u′v′ ∈ E(H).

For each ∅ 6= C ⊆ V (G)× V (H), the G-projection and H-projection of C are, respec-
tively, the sets CG = {x ∈ V (G) : (x, a) ∈ C for some a ∈ V (H)} and
CH = {a ∈ V (H) : (y, a) ∈ C for some y ∈ V (G)}. Observe that any non-empty subset C
of V (G)× V (H) can be written as C = ∪x∈S({x} × Tx) ⊆ V (G[H]), where S ⊆ V (G) and
Tx = {a ∈ CH : (x, a) ∈ C} for all x ∈ S.

2. Total Domination in the Lexicographic Product of Graphs

We shall use the following well-known result.

Lemma 2.1. [1] Let G be a connected graph and S a dominating set of G. Then
γt(G) ≤ |S ∩NG(S)|+ 2|S \NG(S)|. In particular, γt(G) ≤ 2γ(G).



C. Armada, S. Canoy Jr., C. Go / Eur. J. Pure Appl. Math, 12 (4) (2019), 1779-1786 1781

Theorem 2.2. Let G and H be both nontrivial 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 total 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 total dominating set of H for every x ∈ S\NG(S).

Proof. Suppose that C = ∪x∈S({x} × Tx), where S ⊆ V (G) and Tx ⊆ V (H)
for each x ∈ S, is a total dominating set of G[H]. Let u ∈ V (G)\S and pick any
b ∈ V (H). Since (u, b) ∈ V (G[H]) \ C and C is a dominating set of G[H], there exists
(y, c) ∈ C such that (y, c)(u, b) ∈ E(G[H]). This implies that y ∈ S and u ∈ NG(y).
This shows that S is a dominating set of G. If S is a total dominating set of G, then
we are done. So suppose S is not a total dominating set of G. Then S \ NG(S) 6= ∅.
Let x ∈ S \ NG(S). Suppose there exists y ∈ V (H) \ NH(Tx). Then yz /∈ E(H) for all
z ∈ Tx. This implies that (x, y) /∈ NG[H](C), contrary to our assumption that C is a total
dominating set of G[H]. Therefore, NH(Tx) = V (H), i.e., Tx is a total dominating set of
H.

For the converse, let C = ∪x∈S({x} × Tx) and (u, t) ∈ V (G[H]). Assume first that S is
a total dominating set of G. Then there exists x ∈ S \ {u} such that u ∈ NG(x). Choose
d ∈ Tx. Then (x, d) ∈ C and (u, t)(x, d) ∈ E(G[H]). Hence, (u, t) ∈ NG[H](C).

Suppose now that (ii) holds. If u ∈ V (G) \ S, then because S is a dominating set
of G, there exists y ∈ S such that u ∈ NG(y). Pick a ∈ Ty. Then (y, a) ∈ C and
(u, t)(y, a) ∈ E(G[H]). Suppose that u ∈ S. If u ∈ NG(z) for some z ∈ S \ {u}, then
there exists (z, b) ∈ C such that (u, t)(z, b) ∈ E(G[H]). If u /∈ NG(z) for all z ∈ S \ {u},
then by assumption, Tu is a total dominating set of H. Since (u, t) /∈ C, t /∈ Tu. This
implies that there exists s ∈ Tu such that ts ∈ E(H). It follows that (u, s) ∈ C and
(u, t)(u, s) ∈ E(G[H]). Thus, (u, t) ∈ NG[H](C). In both cases, we have shown that
(u, t) ∈ NG[H](C). Therefore, NG[H](C) = V (G[H]), i.e., C is a total dominating set of
G[H]. �

Corollary 2.3. Let G and H be nontrivial connected graphs with γt(H) = 2. Then
C = ∪x∈S({x} × Tx) ⊆ V (G[H]), where S ⊆ V (G) and Tx ⊆ V (H) ∀x ∈ S, is a γt-set
of G[H] if and only if either
(i) S is a γt-set of G and |Tx| = 1 for all x ∈ S; or
(ii) S is a dominating set of G such that |S ∩NG(S)|+ 2|S\NG(S)| = γt(G), |Tx| = 1 for
all x ∈ S ∩NG(S), and Tx is a γt-set of H (hence |Tx| = 2) for every x ∈ S\NG(S).

Proof. Suppose C = ∪x∈S({x} × Tx) is a γt-set of G[H]. By Theorem 2.2, S is a
total dominating set of G or S is a dominating set of G and Tx is a total dominating set
of H for every x ∈ S \ NG(S). Suppose first that S is total dominating set. Suppose
further that that |Tz| ≥ 2 for some z ∈ S. Let a ∈ Tz and define T ∗z = {a}. Then
C∗ = [∪x∈S\{z}({x} × Tx)] ∪ ({z} × T ∗z ) is a total dominating set by Theorem 2.2(i). This,
however, is impossible because |C∗| < |C|. Thus, |Tx| = 1 for all x ∈ S. Thus, (i) holds.

Suppose now that S is a dominating (not a total dominating) set of G. Suppose first
that γt(G) < |S ∩NG(S)|+ 2|S \NG(S)| ≤ |C|. Choose a γt-set R in G and set Sx = {v}



C. Armada, S. Canoy Jr., C. Go / Eur. J. Pure Appl. Math, 12 (4) (2019), 1779-1786 1782

for every x ∈ R, where v ∈ V (H). Then Y = ∪x∈R({x} × Sx) is a total dominating set by
Theorem 2.2(i). It follows that γt(G) = |R| = |Y | < |C|, contrary to our assumption of C.
Thus, by Lemma 2.1, γt(G) = |S ∩NG(S)|+ 2|S \NG(S)|.

Next, suppose that there exists z ∈ S ∩NG(S) with |Tz| ≥ 2. Let a ∈ Tz and define
T ∗z = {a}. Then C∗ = [∪x∈S\{z}({x} × Tx)] ∪ ({z} × T ∗z ) is a total dominating set by
Theorem 2.2(ii). This is not possible because |C∗| < |C| Therefore |Tx| = 1 for all
x ∈ S ∩NG(S). Finally, suppose there exists w ∈ S \NG(S) such that Tw is not a γt-set of
H. Since Tw is a dominating set and γt(H) = 2, |Tw| > 2. Let Lw = {a, b} be a γt-set of
H. Then C1 = [∪x∈S\{w}({x} × Tx)] ∪ ({w} × Lw) is a total dominating set by Theorem
2.2(ii). Again, this is not possible because |C1| < |C|. Therefore, Tx is a γt-set of H for
every x ∈ S \NG(S).
The converse is easy. �

Corollary 2.4. Let G and H be nontrivial connected graphs with γt(H) 6= 2. Then a
subset C = ∪x∈S({x}× Tx) of V (G[H]), where S ⊆ V (G) and Tx ⊆ V (H) for every x ∈ S,
is a γt-set of G[H] if and only if S is a γt-set of G and |Tx| = 1 for all x ∈ S.

Proof. Suppose C = ∪x∈S({x} × Tx) is a γt-set of G[H]. Suppose S is not a total
dominating set. Then S is a dominating set of G and Tx is a total dominating set of H
for every x ∈ S \ NG(S), by Theorem 2.2. Since γt(H) 6= 2, it follows that |Tx| > 2 for
every x ∈ S \NG(S). By Lemma 2.1 and since |C| =

∑
x∈S∩NG(S) |Tx|+

∑
x∈S\NG(S) |Tx|,

it follows that γt(G) < |C|. Let S1 be a γt-set of G and set Qx = {a} for every x ∈ S1,
where a ∈ V (H). Put Q = ∪x∈S1({x} ×Qx). Then Q is a total dominating set of G[H]
by Theorem 2.2(i). Moreover, |Q| = |S1| = γt(G). Thus, |Q| < |C|, contrary to our
assumption of C. Therefore, S is a total dominating set of G. Using a similar argument, it
can be shown that S is a γt-set of G and |Tx| = 1 for all x ∈ S.

For the converse, suppose that C = ∪x∈S({x}×Tx) and S is a γt-set of G with |Tx| = 1
for all x ∈ S. By Theorem 2.2, C is a total dominating set of G[H]. If C1 = ∪x∈S1({x}×Lx)
is another total dominating set of G[H], then, by Theorem 2.2, S1 is dominating set of G
and Lx is a total dominating set of Hx for each x ∈ S1 \NG(S1). Let D1 = S1 ∩NG(S1)
and D2 = S1 \NG(S1). By Theorem 2.2,

|D1|+ 2|D2| ≤
∑

x∈D1

|Lx|+
∑

x∈D2

|Lx| = |C1|.

Thus, by Lemma 2.1, γt(G) = |C| ≤ |C1|. This implies that C is a γt-set of G[H]. �

Corollary 2.5. Let G and H be nontrivial connected graphs. Then

γt(G[H]) = γt(G).

Proof. Let S be a γt-set of G. Pick a ∈ V (H) and set Tx = {a} and
C = ∪x∈S({x} × Tx). By Corollary 2.3 and Corollary 2.4, C is γt-set of G[H]. Thus,
γt(G[H]) = |C| = |S| = γt(G). �

Theorem 2.6. Let G and H be nontrivial connected graphs. Then

fγt(G[H]) = γt(G).



C. Armada, S. Canoy Jr., C. Go / Eur. J. Pure Appl. Math, 12 (4) (2019), 1779-1786 1783

Proof. Let C = ∪x∈S [{x} × Tx] be a γt-set of G[H] and let RC = ∪x∈D[{x} ×Rx] be a
forcing subset for C. First, suppose that S is a γt-set of G. Then |Tx| = 1 for all x ∈ S
by Corollaries 2.3 (i) and 2.4. Hence, Rx = Tx for all x ∈ D. If D 6= S, say y ∈ S\D,
then RC ⊆ C∗ = ∪x∈S [{x} × T ∗x ], where T ∗x = Tx for x ∈ S\{y} and T ∗y is a singleton
subset of H different from Ty. Since C∗ is a γt-set of G[H] and C∗ 6= C, RC is not a
forcing subset for C, contrary to the assumption. Thus, D = S, that is, RC = C. Hence,
fγt(C) = |C| = |S| = γt(G) = fγt(G[H]).

Next, suppose that S is a dominating (not a total dominating) set of G such that
|S ∩NG(S)|+ 2|S\NG(S)| = γt(G). Then |Tx| = 1 for all x ∈ S ∩NG(S) and Tx is a γt-set
of H for each x ∈ S\NG(S) by Corollary 2.3(ii). (Note that in this case, γt(H) = 2). Let
C = C1 ∪ C2 where C1 = ∪x∈S∩NG(S)[{x} × Tx] and C2 = ∪x∈S\NG(S)[{x} × Tx]. Clearly,
S ∩NG(S) ⊆ D, that is, C1 ⊆ RC . Now, choose vy ∈ NG(y) for each y ∈ S \NG(S) and
let FS = {vy : y ∈ S \ NG(S)}. Clearly, S ∩ FS = ∅. Suppose that |FS | < |S \ NG(S)|.
Then there exist distinct y1, y2 ∈ S \NG(S) such that vy1 = vy2 . Let S0 = S ∪ FS . Then

|S0| = |S|+ |FS | < |S ∩NG(S)|+ 2|S\NG(S)| = γt(G).

This is a contradiction because S0 is a total dominating set of G. Thus, |FS | = |S \NG(S)|
(hence, the vy’s are distinct). Next, suppose that there exists q ∈ S \ NG(S) such that
{q} × Tq is not contained in RC . Let Tq = {a, b} and suppose, without loss of generality,
that (q, a) /∈ RC . Let Sq = S ∪ {vq} and set Rq = {b}, Rvq = {a}, Rx = Tx for each
x ∈ S {q}, and Cq = ∪x∈Sq [{x} × Rx]. Then Sq ∩ NG(Sq) = [S ∩ NG(S)] ∪ {q, vq} and
Sq \NG(Sq) = (S \NG(S)) \ {q}. Hence,

|Sq ∩NG(Sq)|+ 2|Sq\NG(Sq)| = |S ∩NG(S)|+ 2 + 2|S\NG(S)| − 2 = γt(G).

Thus, Cq is a γt-set of G[H] by Corollaries 2.3 and 2.4, Cq 6= C, and
RC ⊆ Cq. This implies that RC is not a forcing subset for C, contrary to the assumption that
it is. Therefore C2 ⊆ RC , showing that RC = C. Accordingly,
fγt(G[H]) = |C| = γt(G). �

3. Connected Domination in the Lexicographic Product of Graphs

Theorem 3.1. Let G and H be nontrivial 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 connected dominating set of G[H] if and only if S is a connected dominating set of G,
where Tx is a connected dominating set of H whenever |S| = 1.

Proof. Suppose that C = ∪x∈S({x}×Tx) ⊆ V (G[H]), where S ⊆ V (G) and Tx ⊆ V (H)
for every x ∈ S, is a connected dominating set of G[H]. Then, clearly, S is a dom-
inating set in G. Let x, y ∈ S, where x 6= y and xy /∈ E(G). Let a ∈ Tx and
b ∈ Ty. Then (x, a), (y, b) ∈ C, (x, a) 6= (y, b) and (x, a)(y, b) /∈ E(G[H]). Since 〈C〉
is connected, there exists an (x, a)-(y, b) geodesic [(x1, a1), (x2, a2), . . . , (xk, ak)], where
(x1, a1) = (x, a), (xk, ak) = (y, b), and (xi, ai) ∈ C for all i ∈ {1, 2, . . . , k} (k ≥ 3).



C. Armada, S. Canoy Jr., C. Go / Eur. J. Pure Appl. Math, 12 (4) (2019), 1779-1786 1784

It follows that [x1, x2, . . . , xk], where x1 = x and xk = y, is an x-y geodesic and
xi ∈ S for all i ∈ {1, 2, . . . , k}. This implies that 〈S〉 is connected. Now, suppose
that |S| = 1, say S = {x}. Let a, b ∈ Tx, where a 6= b and ab /∈ E(G). Since
(x, a), (x, b) ∈ C, (x, a) 6= (x, b) and (x, a)(x, b) /∈ E(G[H]), there exists an (x, a) − (x, b)
geodesic [(x, a1), (x, a2), . . . , (x, ak)], where a1 = a, ak = b, and (x, ai) ∈ C for all
i ∈ {1, 2, . . . , k}. It follows that [a1, a2, . . . , ak] is an a-b geodesic and ai ∈ Tx for all
i ∈ {1, 2, . . . , k}. Hence, 〈Tx〉 is connected. Moreover, Tx is a dominating set in H.

For the converse, let C = ∪x∈S({x} × Tx). Assume that S is a
connected dominating set of G, and that Tx is a connected dominating set of H
whenever |S| = 1. Assume first that |S| ≥ 2 and let (z, c) /∈ C. Since 〈S〉 is con-
nected, there exists w ∈ S such that wz ∈ E(G). Let d ∈ Tw. Then (w, d) ∈ C and
(z, c)(w, d) ∈ E(G[H]). Thus, C is a dominating set in G[H]. Next, let (u, s), (v, t) ∈ C,
where (u, s) 6= (v, t) and (u, s)(v, t) /∈ E(G[H]). If u = v, then we choose w ∈ S such
that uw ∈ E(G). Let q ∈ Tw. Then (w, q) ∈ C and [(u, s), (w, q), (v, t)] is a (u, s)− (v, t)
geodesic. If u 6= v, then there exists a u − v geodesic [u1, u2, . . . , uk] where u1 = u,
uk = v and ui ∈ S for each i ∈ {1, 2, . . . , k}, since 〈S〉 is connected. Choose si ∈ Tui for
each i ∈ {1, 2, . . . , k}, where s1 = s and sk = t. Then [(u1, s1), (u2, s2), . . . , (uk, sk)] is a
(u, s)− (v, t) geodesic and (ui, si) ∈ C for each i ∈ {1, 2, . . . , k}. Thus, 〈C〉 is connected.
It is easy to show that C is a connected dominating set if S = {x} is a dominating set and
Tx is a connected dominating set in H. �

Corollary 3.2. Let G and H be nontrivial connected graphs with γ(G) = 1. Then

γc(G[H]) =
{

1, γ(H) = 1
2, otherwise.

Proof. Let {x} be a dominating set in G. If γ(H) = 1, then choose a dominating set {d}
in H. Clearly, C0 = {(x, d)} is a connected dominating set of G[H]. Hence, γc(G[H]) = 1.
Suppose that γ(H) ≥ 2 and let S = {x, y} with xy ∈ E(G). Choose any a ∈ V (H). Then
C = {(x, a), (y, a)} is a connected dominating set of G[H] by Theorem 3.1. Since G[H]
cannot be dominated by a single vertex, it follows that γc(G[H]) = |C| = 2. �

Corollary 3.3. Let G and H be nontrivial connected graphs with γ(G) 6= 1. Then

γc(G[H]) = γc(G).

Proof. Let S be a minimum connected dominating set in G. Choose any a ∈ V (H)
and set Tx = {a} for each x ∈ S. Then C = ∪x∈S({x} × Tx) is a minimum connected
dominating set of G[H] by Theorem 3.1. Therefore, γc(G[H]) = |C| = |S| = γc(G). �

Theorem 3.4. Let G and H be nontrivial connected graphs with γ(G) = 1 and γ(H) = 1.
Then

fγc(G[H]) =
{

0, both G and H have unique γ-sets,
1, otherwise.



REFERENCES 1785

Proof. Suppose that both G and H have unique γ-sets, say S and T , respectively.
Then S and T are also γc-sets. By Theorem 3.1, C = ∪x∈S({x} × Tx) ⊆ V (G[H]), where
S ⊆ V (G) and Tx ⊆ V (H) for every x ∈ S, is the only γc-set of G[H], that is, ∅ is a
forcing subset for C. Thus, fγc(G[H]) = fγc(C) = 0.

Suppose that either G or H has no unique γ-set (γc-set). Then by Theorem 3.1,
C = {(x, y) : x ∈ S and y ∈ Tx}, where S is a γc-set of G and Tx is a γc-set of H, is not a
unique γc-set of G[H]. By Corollary 3.2, |C| = 1, that is, C is a forcing subset for itself.
Thus, fγc(G[H]) = fγc(C) = 1. �

Theorem 3.5. Let G and H be nontrivial connected graphs with γ(G) = 1 and γ(H) > 1.
Then

fγc(G[H]) = 2.

Proof. Note that by Corollary 3.2, γc(G[H]) = 2. Let S = {x, y} be a γc-set
of G. Choose any vertex a ∈ V (H). Then C = {(x, a), (y, a)} is a γc-set of G[H]
by Theorem 3.1. Pick b ∈ V (H)\{a}. Then {(x, a)} ⊆ C ′ = {(x, a), (y, b)} and
{(y, a)} ⊆ C∗ = {(x, b), (y, a)}, where C ′ and C∗ are also γc-sets of G[H] different from C.
Thus, fγc(C) = 2 = fγc(G[H]). �

Theorem 3.6. Let G and H be nontrivial connected graphs with γ(G) 6= 1. Then

fγc(G[H]) = γc(G).

Proof. Let C = ∪x∈S [{x} × Tx] be a γc-set of G[H] and let PC = ∪x∈D[{x} × Px] be a
forcing subset for C. First, suppose that S is a γc-set of G. Then |Tx| = 1 for all x ∈ S by
Theorem 3.1 and Corollary 3.3. Hence, Px = Tx for all x ∈ D. If D 6= S, say y ∈ S\D,
then PC ⊆ C∗ = ∪x∈S [{x} × T ∗x ], where T ∗x = Tx for x ∈ S\{y} and T ∗y is a singleton
subset of H different from Ty. Since C∗ is a γc-set of G[H] and C∗ 6= C, PC is not a
forcing subset for C, contrary to the assumption. Thus, D = S, that is, PC = C. Hence,
fγc(C) = |C| = |S| = γc(G) = fγc(G[H]). �

Acknowledgements

The authors would like to thank the referees for their invaluable suggestions and com-
ments which greatly contributed in the improvement of the paper. The authors would like to
thank also the following funding agencies:
Department of Science and Technology-Science Education Institute-Accelerated Science and
Technology Human Resource Development Program (DOST-SEI-ASTHRDP), Mindanao
State University-Iligan Institute of Technology, Cebu Normal University and Commission
on Higher Education, Philippines.

References

[1] C. Armada, S. Canoy Jr., and C. Go, Forcing Domination Numbers of Graphs Under
Some Binary Operations, Advances and Applications in Discrete Mathematics, 19:
213-228, 2018



REFERENCES 1786

[2] G. Chartrand, H. Gavlas, K.C. Vandell, and F. Harary, The Forcing Domination
Number of a Graph, J.Combin. Math. Combin. Comput., 25:161-174, 1997

[3] J. John, S. Kavitha and S. Robinson Chellathurai. On the forcing connected domination
number of a graph. Journal of Discrete Mathematical Sciences and Cryptography,
20:611?624, 2017.