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

On Independent Transversal Dominating Sets in Graphs

Daven S. Sevilleno1,∗, Ferdinand P. Jamil2

1 Department of Mathematics and Statistics, College of Liberal Arts, Sciences and Education,
University of San Agustin, 5000 Iloilo City Philippines
2 Department of Mathematics and Statistics, College of Science and Mathematics,
Center of Graph Theory, Algebra and Analysis, Premier Research Institute of Science and
Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City,
Philippines

Abstract. A set S ⊆ V (G) is an independent transversal dominating set of a graph G if S is
a dominating set of G and intersects every maximum independent set of G. An independent
transversal dominating set which is a total dominating set is an independent transversal total
dominating set. The minimum cardinality γit(G) (resp. γitt(G)) of an independent transversal
dominating set (resp. independent transversal total dominating set) of G is the independent
transversal domination number (resp. independent transversal total domination number) of G. In
this paper, we show that for every positive integers a and b with 5 ≤ a ≤ b ≤ 2a− 2, there exists
a connected graph G for which γit(G) = a and γitt(G) = b. We also study these two concepts in
graphs which are the join, corona or composition of graphs.

2020 Mathematics Subject Classifications: 05C22, 05C69, 05C776
Key Words and Phrases: Independent transversal dominating set, Independent transversal
total dominating set, Independent transversal domination number, Independent transversal total
domination number

1. Introduction

Throughout this paper, by a graph G = (V (G), E(G)) is meant a finite, simple
and connected graph with V (G) and E(G) being the vertex set and edge set, respectively.
For S ⊆ V (G), |S| is the cardinality of S. In particular, |V (G)| is called the order of G.
All basic terminologies used here are adapted from [4].

Given two graphs G and H with disjoint vertex sets,

• the union of G and H, denoted G ∪H, is the graph with vertex set V (G) ∪ V (H)
and edge set E(G) ∪ E(H);

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i1.3904

Email addresses: daven.sevilleno@g.msuiit.edu.ph (D. Sevilleno),
ferdinand.jamil@g.msuiit.edu.ph (F. Jamil)

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



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 150

• the join of G and H is the graph G+H with vertex set V (G) ∪ V (H) and edge set
E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)};

• the corona of G and H is the graph G ◦ H obtained by taking one copy of G and
|V (G)| copies of H, and then joining the ith vertex of G to every vertex in the ith

copy of H; and

• the composition G[H] of G and H is the graph with V (G[H]) = V (G)× V (H) and
(u, v)(u′, v′) ∈ E(G[H]) if and only if either uu′ ∈ E(G) or u = u′ and vv′ ∈ E(H).

For corona of graphs G ◦H, if H = K1, we write G ◦H = cor(G). It is customary to
denote by Hv that copy of H whose vertices are joined with the vertex v of G. Similarly,
we also write uv to denote that copy of u ∈ V (H) in Hv.

For vertices u and v of G, a u-v geodesic is any shortest u-v path. The distance between
u and v is the length of a u-v geodesic, and is denoted by dG(u, v). The eccentricity of
v, denoted by e(v), is given by e(v) = max{dG(u, v) : u ∈ V (G)}. The diameter of G,
denoted by diam(G), is defined by diam(G) = max{dG(u, v) : u, v ∈ V (G)}. Any geodesic
of length diam(G) is called diametral path of G.

Vertices u and v of a graph G are neighbors if uv ∈ E(G). The open neighborhood
of v refers to the set NG(v) consisting of all neighbors of v. The closed neighborhood of
v is the set NG[v] = NG(v) ∪ {v}. For S ⊆ V (G), NG(S) = ∪v∈SNG(v) and NG[S] =
∪v∈SNG[v]. A subset S ⊆ V (G) is a dominating set of G if NG[S] = V (G). The minimum
cardinality γ(G) of a dominating set in G is the domination number of G. We refer to
[1, 2, 5, 7, 9, 11, 14, 16, 19] for the history, fundamental concepts and the subsequent
developments of domination in graphs as well as its various applications.

Provided G has no isolated vertices, a dominating set S is a total dominating set of G
if every vertex in S is adjacent to another vertex in S. The minimum cardinality of a total
dominating set of G is the total domination number of G denoted by γt(G). References
[6, 8, 12] are excellent studies on total domination in graphs.

A subset S ⊆ V (G) is an independent set of G if for every distinct vertices u and v in
S, uv /∈ E(G). The maximum cardinality of an independent set is called the independence
number of G, and is denoted by β0(G). Any independent set of cardinality β0(G) is referred
to as a β0-set of G. In [13], it is called a maximum independent set. It is worth noting
that if G is complete, then {v} is a β0-set for all v ∈ V (G). The symbol XI(G) denotes
the family of all β0-sets of G, and xi(G) = |XI(G)|.

A subset S ⊆ V (G) of G is said to be an independent transversal set of G if S intersects
every β0-set of G. The minimum cardinality of an independent transversal set of G is called
the independent transversal number, denoted by β0t(G). In particular, β0t(Kn) = n; for
path Pn, β0t(Pn) = 1 when n is odd and β0t(Pn) = 2 otherwise; for cycle Cn on n ≥ 3
vertices, β0t(Cn) = 2 when n is even and β0t(Cn) = 3 otherwise; and for the complete
bipartite Km,n, β0t(Km,n) = 1 if m 6= n, and β0t(Km,n) = 2 otherwise..

An independent transversal set of G is an independent transversal dominating set or
(ITD-set) if S is a dominating set of G. The minimum cardinality of an ITD-set of G is
called the independent transversal domination number of G and is denoted by γit(G). An



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 151

ITD-set S of G with |S| = γit(G) is called a γit-set. The study on independent transversal
domination in graphs was initiated by I. Hamid [10] in 2012. It was studied further by
Yero et al. [17, 18, 20] in 2016, 2017 and 2021, and by Ozeki et al. [3] in 2018.

Provided G has no isolated vertex, a subset S ⊆ V (G) is an independent transversal
total dominating set or (ITTD-set) if S is both an ITD-set and a total dominating set of
G. We denote by γitt(G) the minimum cardinality of an ITTD-set of G, and is called the
independent transversal total domination number of G. In [17], Cabrera Martinez et al.
made a good introduction of this concept. The authors prove that the complexity of the
decision problem associated to the computation of the value of γitt(G) is NP-complete,
under the assumption that the independence number is known.

Henceforth, all discussions of total domination or independent transversal total domi-
nation are always with respect to graphs without isolated vertices.

For graphs G of order n ≥ 2, γit(G) ≤ γitt(G).

2. Preliminaries and Known Results

Observation 1. (i) For the complete bipartite Km,n, γit(Km,n) = γitt(Km,n) = 2.

(ii) For any path Pn of order n ≥ 2, we have

(a) [10] γit(Pn) =


2 if n = 2, 3,

3 if n = 6,

dn3 e otherwise,
and

(b) γitt(Pn) =


3 if n = 4,
n
2 + 1 if n ≡ 2(mod 4),

dn2 e, otherwise

(iii) For any cycle Cn of order n ≥ 3, we have

(a) [10]γit(Cn) =

{
3 if n = 3, 5,

dn3 e otherwise,
and

(b) γitt(Cn) =


3 if n = 3,
n
2 + 1 if n ≡ 2(mod 4),

dn2 e, otherwise.

Theorem 1. For any graph G, we have

(i) [10] γ(G) ≤ γit(G) ≤ γ(G) + δ(G); and

(ii) [17] γt(G) ≤ γitt(G) ≤ γt(G) + δ(G).

Corollary 1. Let G be a graph.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 152

(i) [10] If G has an isolated vertex, then γit(G) = γ(G).

(ii) If G has K2 as a component, then γitt(G) = γt(G).

If follows from Observation 1 that if G = P3n−2, then γit(G) = γ(G) = n. Thus, the
following corollary is clear.

Corollary 2. For all positive integers n, there exists a connected graph G for which
γ(G) = γit(G) = n.

Observation 2. Let G be a connected graph of order n. Then

(i) γit(G) = n if and only if G = Kn. Provided n ≥ 2, γitt(G) = n if and only if
G = Kn.

(ii) For n ≥ 3,

(a) γit(G) = n− 1 if and only if G = P3.

(b) γitt(G) = n− 1 if and only if G = P3 or G = P4.

(iii) γit(G) = 2 if and only if either G = K2 or G has a dominating set {u, v} such that
every β0-set contains u or v.

(iv) γitt(G) = 2 if and only if either G = K2 or G has a total dominating set {u, v} such
that every β0-set contains either u or v.

(v) γit(G) = 1 if and only if n = 1.

In Observation 2(iii), a β0-set may contain both u and v. Consider, for example, the
graph G = Kn−1 + v for n ≥ 2.

3. Realization Problems

Theorem 2. [20] For every positive integers a, b, c such that c ≥ 2 and a ≤ b ≤ a + c,
there exists a graph G such that δ(G) = c, γ(G) = a and γit(G) = b.

Theorem 3. [17] For any two positive integers a and b such that 2 ≤ a ≤ 2b
3 , there is a

graph of order b such that γitt(G) = a.

Theorem 4. For any positive integers a and b with 3 ≤ a ≤ b there exists a connected
graph G for which γt(G) = a and γitt(G) = b.

Proof. We consider the following cases:

Case 1: Suppose that a = b. If a = b = 3, then we choose G = C5. Suppose that
a = b ≥ 4. If a ≡ 0, 2(mod 4), then choose G = P2a. If a ≡ 1, 3(mod 4), then choose
G = P2a−1. In any case, γt(G) = γitt(G) = a.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 153

· · ·

· · · · · ·

· · ·

· · ·

· · ·

· · ·

Figure 1: Graph G = Ca ◦ {Kn ∪Kn} with a ≥ 3

Case 2: Suppose that a < b. The b = a + n for some positive integer n. Consider the
corona G = Ca ◦ {Kn ∪Kn} as shown in Figure 1. For convenience, write (Kn ∪Kn)v =
Kv
n ∪ Kv

n. Clearly, V (Ca) is a γt-set of G so that γt(G) = a. Let v ∈ V (Ca) and define
S = V (Ca)∪V (Kv

n). Then, S is a total dominating set of G. Now a β0-set M of G is of the
form M = ∪v∈V (Ca){av, bv}, where av and bv belong to different components of Kv

n ∪Kv
n.

Then M ∩ S 6= ∅. Thus, S is an ITTD-set of G. Thus, γitt(G) ≤ |S| = a + n = b. Let
T ⊆ V (G) be a total dominating set with |T | < b. Then V (Kv

n)\T 6= ∅ for all v ∈ V (Ca).
For each v ∈ V (Ca), pick av, bv ∈ V (Kv

n ∪Kv
n) \ T such tha av and bv are from different

components. Then M = {av, bv : v ∈ V (G)} is a maximum independent set of G. Since
M ∩ T = ∅, T is not an ITTD-set of G. Since T is arbitrary, γitt(G) = b.

Theorem 5. For every positive integers n, a and b with 5 ≤ a ≤ b ≤ 2a− 2, there exists
a connected graph G for which γit(G) = a and γitt(G) = b.

Proof. For k ≥ 2, denote by G(k) the graph given in Figure 2.

x1 x2 x3 x4 xk
· · ·

x2 x3 x4 xk

Figure 2: Graph G(k)

Suppose that a = b. Take the graph G as in Figure 3 obtained from the graph G(a−1)
by adding the path [xa−1, xa, xa+1, xa+2, x

a+2]. Observe that {x2, x3, ..., xa−1, xa+2} is a

xa+1 xa+2

xa+2

x1 x2 x3 x4 xa−1 xa
· · ·

x2 x3 x4 xa−1

Figure 3: Graph G with γit(G) = γitt(G)

γ-set of G and every maximum independent set of G contains either xa+2 or xa+2. Thus,



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 154

the set D = {x2, x3, ..., xa−1, xa+2, x
a+2} is a γit-set of G. Note that [x2, x3, ..., xa−1] is a

path of length at least 2. Hence D is also a γitt-set of G. Therefore γit(G) = γitt(G) =
(a− 2) + 2 = a.

Suppose now that a < b. Then b = a + k for some positive integer 1 ≤ k ≤ a − 2.
For k = 1, consider the graph G in Figure 4 obtained from G(a − 2) by adding the
paths [xa−2+3j , xa−1+3j , xa+3j , xa+1+3j , x

a+1+3j ] where j = 0, 1. By a similar argument

xa xa+1

xa+1

x1 x2 x3 x4 xa−2 xa−1 xa+2 xa+3 xa+4

xa+4

· · ·

x2 x3 x4 xa−2

Figure 4: Graph G with γitt(G) = γit(G) + 1

D = {x2, x3, ..., xa−2, xa+1, xa+4, x
a+4} is a γit-set of G. This implies that γit(G) = (a −

3) + 3 = a. It also follows that D ∪ {xa+1} is a γitt-set of G. Thus, γitt(G) = a+ 1 = b.

For 2 ≤ k ≤ a−4, consider the graph G in Figure 5 obtained from G(a−k−1) by adding
(k + 1) paths [xa−k−1+3j , xa−k+3j , xa−k+1+3j , xa−k+2+3j , x

a−k+2+3j ] (j = 0, 1, · · · , k − 1)
and [xa+2k, xa+2k+1, xa+2k+2, xa+2k+3, xa+2k+4, xa+2k+5]. ThenD = {x2, x3, . . . , xa−k−1}∪

xa−k+2

xa−k+2

x1 x2 x3 x4 xa−k−1 xa−k+5

xa−k+5

· · ·

x2 x3 x4 xa−k−1

· · ·
xa+2k−4

xa+2k−4

xa+2k−1

xa+2k−1

xa+2k+2

xa+2k+3

xa+2k+4

Figure 5: Graph G with γitt(G) = γit + k, where 2 ≤ k ≤ a− 4

{xa−k+2+3j : j ∈ {0, 1, 2, . . . , k − 1}} ∪ {xa+2k+2, xa+2k+4} is a γit-set of G. On the other
hand, D ∪ {xa−k+2+3j : j ∈ {0, 1, 2, . . . , k − 1}} ∪ {xa+2k+3} is a γitt-set of G. Thus,
γit(G) = (a− k − 2) + k + 2 = a and γitt(G) = a+ k = b.

For k = a − 3, consider the graph G in Figure 6 obtained from G(2), by adding
(a − 2) paths [x2, x3, x4, x

4], [x4+3j , x5+3j , x6+3j , x7+3j , x
7+3j ], j = 0, 1, 2, ..., a − 5, and

[xa+2k−2, xa+2k−1, xa+2k, xa+2k+1, xa+2k+2, xa+2k+3]. ThenD = {x2}∪{x4+3j |j = 0, 1, 2, ...,
a − 4} ∪ {xa+2k+1, xa+2k+2} is a γit-set of G. On the other hand, D ∪ {x3} ∪ {x4+3j |j =
0, 1, 2, ..., a − 4} is a γitt-set of G. Thus, γit(G) = 1 + a − 3 + 2 = a, and γitt(G) =
a+ (a− 3) = a+ k.

Now, for k = a − 2, consider the graph G as in Figure 7 obtained by adding (a − 2)
P5 paths [x2+3j , x3+3j , x4+3j , x5+3j , x

5+3j ], j = 0, 1, . . . , a − 3, to the path G(2). Then
D = {x3a−4, x3a−4, x2+3j : j ∈ {0, 1, 2, . . . , a − 3}} is a γit-set of G, and D ∪ {x2+3j : j ∈
{0, 1, 2, . . . , a − 3}} forms a γitt-set of G. Therefore, γit(G) = 2 + (a − 2) and γitt(G) =
a+ (a− 2) = b.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 155

x6 x7

x7

x1 x2 x4 x5 x8 x9 x10

x10

x3

x2 x4

· · ·

xa+2k−5

xa+2k−5

xa+2k−2

xa+2k−2 xa+2k+1

xa+2k+2

xa+2k+3

Figure 6: Graph G with γitt(G) = γit(G) + a− 3

x7 x8

x8

x1 x2 x3 x4 x5 x6 x9 x10 x11

x11x2 x5

x12
· · ·

x3k−5x3k−4

x3k−4

Figure 7: Graph G with γitt(G) = γit(G) + a− 2

4. On join of graphs

For an independent subset D ⊆ V (G + H), either D ⊆ V (G) or D ⊆ V (H). In
particular, if β0(H) < β0(G), then D is a β0-set of G+H if and only if D ⊆ V (G) and is
a β0-set of G.

Proposition 1. Let G and H be connected graphs with β0(H) < β0(G). Then D ⊆
V (G + H) is an independent transversal (total) dominating set of G + H if and only if
one of the following holds:

(i) D ⊆ V (G) and D is an independent transversal (total) dominating set of G;

(ii) D ∩ V (G) is an independent transversal set of G and D ∩ V (H) 6= ∅.

Proof. Let D ⊆ V (G + H). Assume that D is an independent transversal (total)
dominating set of G + H. In view of the preceding remark, D ∩ V (G) 6= ∅. Suppose
that D ⊆ V (G). Then D is a (total) dominating set of G. Let M ⊆ V (G) be a β0-
set of G. Then M is a β0-set of G + H. Thus, D ∩ M 6= ∅. This shows that D is
an independent transversal (total) dominating set of G. Suppose that D intersects both
V (G) and V (H), and let M ⊆ V (G) be a β0-set of G. Since M is a β0-set of G + H,
M ∩ (D ∩ V (G)) = M ∩D 6= ∅. Thus, D ∩ V (G) is an independent transversal set of G.

Conversely, since (total) dominating sets of G are (total) dominating sets of G + H,
in view of the preceding remark, if (i) holds for D ⊆ V (G), then D is an independent
transversal (total) dominating set of G + H. Suppose that (ii) holds for D. Then D is
a (total) dominating set of G + H. Let M ⊆ V (G + H) be a β0-set of G + H. Then
M ⊆ V (G) and is a β0-set of G. Thus, D ∩M = (D ∩ V (G)) ∩M 6= ∅. This shows that
D is an independent transversal (total) dominating of G+H.

Proposition 2. Let G and H be connected graphs with β0(G) = β0(H). Then D ⊆
V (G + H) is an independent transversal (total) dominating set of G + H if and only if
D ∩ V (G) and D ∩ V (H) are independent transversal sets of G and H, respectively.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 156

Proof. Let D ⊆ V (G+H). Suppose that D is an ITD-set of G+H. We claim that D
intersects both V (G) and V (H) so that D is in fact an ITTD-set of G+H. Suppose not,
say D ⊆ V (G). Pick a β0-set M ⊆ V (H) of H. Since M is a β0-set of G+H, D∩M 6= ∅,
which is impossible.

Now, for all β0-sets M ⊆ V (G) of G, M is a β0-set of G+H so that (D ∩ V (G))∩M =
D∩M 6= ∅. This means that D∩V (G) is an independent transversal set of G. Similarly,
D ∩ V (H) is an independent transversal set of H.

Conversely, suppose that D ∩ V (G) and D ∩ V (H) are independent transversal sets of
G and H, respectively. Then D is a total dominating set of G+H. Let M ⊆ V (G+H)
be a β0-set of G + H. Either M ⊆ V (G) and is a β0-set of G or M ⊆ V (H) and is a
β0-set of H. Either case yields D∩M 6= ∅. Thus, D is an independent transversal (total)
dominating set of G+H.

Corollary 3. Let G and H be connected graphs with β0(H) ≤ β0(G). Then the following
hold:

(i) If β0(H) = β0(G), then γit(G+H) = γitt(G+H) = β0t(G) + β0t(H).

(ii) If β0(H) < β0(G) and β0t(G) < γit(G), then γit(G+H) = γitt(G+H) = 1 +β0t(G).

(iii) If β0(H) < β0(G) and β0t(G) = γit(G) = γitt(G), then γit(G+H) = γitt(G+H) =
γit(G).

(iv) If β0(H) < β0(G) and β0t(G) = γit(G) < γitt(G), then γit(G + H) = γit(G) and
γitt(G+H) = 1 + β0t(G).

Proof. The case where β0(G) = β0(H) is immediate from Proposition 2. Assume that
β0(G) > β0(H). It follows from Proposition 1 that γit(G+H) = min{γit(G), 1 + β0t(G)}.
Suppose that γit(G) > β0t(G). Then γit(G + H) = 1 + β0t(G) and any γit-set of G + H
is a total dominating set of G + H. Thus, γitt(G + H) = 1 + β0t(G). Suppose that
γit(G) = β0t(G). If γit(G) = γitt(G), then γitt(G + H) = γit(G + H) = γit(G). Suppose
that γit(G) < γitt(G). Then 1 + β0t(G) ≤ γitt(G). In view of Proposition 1, γitt(G+H) =
1 + β0t(G).

Example 1. (1) For positive integers m,n and p with p > max{m,n},

γit(Km,p +Kn,p) = γitt(Km,p +Kn,p) = 2.

(2) For the fan Fn on n+ 1 ≥ 3 vertices,

γit(Fn) =

{
2, if n = 4 or n is odd;

3, if n is even and n 6= 4,
and γitt(Fn) =

{
2, if n is odd;

3, if n is even.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 157

(3) For the wheel Wn on n+ 1 vertices,

γit(Wn) =


2, if n = 4;

3, if n ∈ {3, 5, 7, 9} or n is even and n 6= 4;

4, otherwise,

and

γitt(Wn) =


2, if n = 4;

3, if n ∈ {3, 5} or n is even and n 6= 4;

4, otherwise.

(4) For all positive integers n ≥ 2 and p ≥ 2, γit(Kn,n +Kp) = γitt(Kn,n +Kp) = 2.

5. On corona of graphs

It is worth noting that G ◦H is composed of the joins Hv + v = Hv + 〈v〉, v ∈ V (G),
joined together by the edges of G. Thus,

V (G ◦H) = V (G) ∪
(
∪v∈V (G)V (Hv)

)
= ∪v∈V (G)V (Hv + v).

Theorem 6. [5] Let G be a connected graph and H any graph. Then S ⊆ V (G ◦H) is a
dominating set of G ◦H if and only if S ∩ V (Hv + v) is a dominating set of Hv + v for
each v ∈ V (G).

Observation 3. Let G be a nontrivial connected graph of order n, and let p be a positive
integer. Then

γit(G ◦Kp) =

{
n, if p = 1;

n+ p, if p ≥ 2,
and γitt(G ◦Kp) = n+ p.

A sharp bound for γit(G ◦H) is provided in [20]

Theorem 7. [20] Let G be a graph of order n ≥ 2. Then for any graph H such that
β0(H) ≥ 2,

n− 1 + dβ(H) ≤ γit(G ◦H) ≤ n+ dβ(H),

where dβ(H) is the largest number of pairwise disjoint β0-sets of H. Moreover, if there is
a dβ(H)-set which is a dominating set in H, then γit(G ◦H) = n− 1 + dβ(H).

Observe that dβ(H) ≤ β0t(H) for any graph H. In what follows, we determine γit(G ◦
H) in terms of β0t(H).

Lemma 1. Let G be a connected graph and H a noncomplete graph. Then a subset
S ⊆ V (G ◦H) is a β0-set of G ◦H if and only if S = ∪v∈V (G)Sv, where Sv ⊆ V (Hv) is a
β0-set of H

v for each v ∈ V (G).



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 158

Proposition 3. Let G and H be nontrivial connected graphs with H noncomplete. Then
S ⊆ V (G◦H) is an ITD-set of G◦H if and only if S = A∪

(
∪v∈V (G)Sv

)
, where A ⊆ V (G)

and Sv ⊆ V (Hv) for all v ∈ V (G) satisfying the following:

(i) For each v ∈ V (G) \A, Sv is a dominating set of Hv.

(ii) There exists v ∈ V (G) for which Sv is an independent transversal set of Hv.

Proof. Assume that S ⊆ V (G◦H) is an ITD-set of G◦H. Then S = A∪
(
∪v∈V (G)Sv

)
,

where A = S ∩ V (G) and Sv = S ∩ V (Hv) for all v ∈ V (G). Statement (i) follows
immediately from Theorem 6. To prove (ii), suppose that for each v ∈ V (G) there exists
a β0-set Mv of Hv for which Sv ∩Mv = ∅. By Lemma 1, M = ∪v∈V (G)Mv is a β0-set of
G◦H. Since S is an independent transversal set of G◦H, ∪v∈V (G) (Sv ∩Mv) = S∩M 6= ∅,
which is impossible. This proves (ii).

Conversely, assume that (i) and (ii) hold for S. By condition (i) and the fact that
S ∩ V (Hv + v) is a dominating set in Hv + v whenever v ∈ A, S is a dominating set of
G ◦H. Let M ⊆ V (G ◦H) be a β0-set of G ◦H. By (ii), there exists v ∈ V (G) for which
Sv is an independent transversal set of Hv. Since Mv = M ∩ V (Hv) is a β0-set of Hv,
Sv ∩Mv 6= ∅. Thus, S ∩M 6= ∅. Therefore, S is an ITD-set of G ◦H.

In view of Proposition 3, the following assertion is clear.

Proposition 4. Let G and H be nontrivial connected graphs with H noncomplete. Then
S ⊆ V (G ◦ H) is an independent transversal total dominating set of G ◦ H if and only
if S = A ∪v∈V (G) Sv, where A ⊆ V (G) and Sv ⊆ V (Hv) for all v ∈ V (G) satisfying the
following:

(i) For each v ∈ V (G) \A, Sv is a total dominating set of Hv.

(ii) For each v ∈ A, Sv 6= ∅ or NG(v) ∩ S 6= ∅.

(iii) There exists v ∈ V (G) for which Sv is an independent transversal set of Hv.

Corollary 4. Let G and H be nontrivial connected graphs, where G is of order n and H
noncomplete.Then

γit(G ◦H) = n− 1 + min{γit(H), 1 + β0t(H)}, (1)

and
γitt(G ◦H) = n− 1 + min{γitt(H), 1 + β0t(H)}. (2)

Proof. Let v ∈ V (G) and let B1, B2 ⊆ V (Hv) be a γit-set and a β0t-set of Hv,
respectively. Put S1 = (V (G) \ {v})∪B1 and S2 = V (G)∪B2. By Proposition 3, both S1
and S2 are ITD-sets of G◦H. Thus, γit(G◦H) ≤ min{|S1|, |S2|} = n−1+min{γit(H), 1+
β0t(H)}.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 159

Let S = A ∪
(
∪v∈V (G)Sv

)
⊆ V (G ◦ H) where A ⊆ V (G) be a γit-set of G ◦ H. By

Proposition 3, |Sw| ≥ 1 for all w ∈ V (G) \A and there exists v ∈ V (G) for which Sv is an
independent transversal set of Hv. We consider two cases:

Case 1: Suppose that v ∈ A. Then

γit(G ◦H) = |S| = |A|+
∑

w∈V (G)

|Sw|

≥ n+ |Sv|
≥ n− 1 + min{γit(H), 1 + β0t(H)}.

Case 2: Suppose that v /∈ A. Then Sv is an ITD-set of Hv. Thus,

γit(G ◦H) = |S| = |A|+
∑

w∈V (G)

|Sw|

≥ n− 1 + |Sv|
≥ n− 1 + min{γit(H), 1 + β0t(H)}.

This proves Equation 1.

Similar arguments will prove Equation 2.

6. On composition of graphs

For a subset C ⊆ V (G[H]), we can always write C = ∪x∈A({x} × Ax) for some
A ⊆ V (G) and Ax = {y ∈ V (H) : (x, y) ∈ A}.

Theorem 8. [15] Let G and H be connected graphs, and C = ∪x∈S ({x} × Sx) ⊆ V (G[H]).
Then C is a dominating set of G[H] if and only if one of the following holds:

(i) S is a total dominating set of G;

(ii) S is a dominating set of G and Sx is a dominating set of H for each x ∈ S \NG(S).

Lemma 2. Let G and H be nontrivial connected graphs, and C = ∪x∈S ({x} × Sx) ⊆
V (G[H]). Then C is an (maximum) independent set of G[H] if and only if S is an
(maximum) independent set of G and Sx is an (maximum) independent set of H for each
x ∈ S.

Proposition 5. Let G and H be nontrivial connected graphs, and C = ∪x∈S ({x} × Sx) ⊆
V (G[H]). Then C is an independent transversal dominating set of G[H] if and only if
each of the following holds:

(i) One of the following holds:

(a) S is an ITTD-set of G.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 160

(b) S is an ITD-set of G and Sx is a dominating set of H for each x ∈ S \NG(S).

(ii) For every pair of β0-sets A and B of G and H, respectively, there exists x ∈ S ∩ A
for which B ∩ Sx 6= ∅.

Proof. Suppose that conditions (i) and (ii) hold for S. Condition (i) implies that C
is a dominating set of G[H] by Theorem 8. Let D = ∪x∈A ({x} ×Ax) ⊆ V (G[H]) be a
β0-set of G[H]. By Lemma 2, A is a β0-set of G and Ax is a β0-set of H for each x ∈ A.
Since S is an ITD-set of G, S ∩A 6= ∅. By condition(ii), there exists x ∈ S ∩A for which
Sx∩Ax 6= ∅. Let y ∈ Sx∩Ax. Then (x, y) ∈ C∩D. Since D is arbitrary, C is an ITD-set
of G[H].

Conversely, assume that C is an ITD-set of G[H]. By Theorem 8, since C is a dom-
inating set of G[H], S is a dominating set of G and Sx a dominating set of H for each
x ∈ S \ NG(S) or S is a total dominating set of G. Let A ⊆ V (G) be a β0-set of G and
B ⊆ V (H) a β0-set of H. Since C∗ = ∪x∈A ({x} ×B) is a β0-set of G[H], C ∩ C∗ 6= ∅.
Let (x, y) ∈ C ∩ C∗. Then x ∈ S ∩ A. So far, we have shown that S is an ITD-set of G,
thus (i) holds. Moreover, y ∈ Sx ∩B so that Sx ∩B 6= ∅. This proves (ii).

It should be noted that if S ∩ A = {x} (singleton) in Theorem 5(ii), then Sx is an
independent transversal set of H.

Consider G = P5[P4]. Write P5 = [x1, x2, x3, x4, x5] and P4 = [y1, y2, y3, y4]. Then
C = {(x2, y2), (x3, y1), (x3, y2), (x4, y2)} is a γit-set of G. Put S = {x2, x3, x4} and A =
{x1, x3, x5}. Then S is a γitt-set of P5 and A is the unique β0-set of P5. Further, S ∩A =
{x3} and Sx3 = {y1, y2} is an independent transversal set of P4.

The following is immediate from Proposition 5.

Proposition 6. Let G and H be nontrivial connected graphs, and C = ∪x∈S ({x} × Sx) ⊆
V (G[H]). Then C is an independent transversal total dominating set of G[H] if and only
if each of the following holds:

(i) S is an independent transversal total dominating set of G.

(ii) For every pair of maximum independent sets A and B of G and H, respectively,
there exists x ∈ S ∩A for which B ∩ Sx 6= ∅.

Given an ITD-set (resp. ITTD-set) S ⊆ V (G) of G, define MG(S) (resp. M t
G(S))

to be any subset of S of minimum cardinality such that for each x ∈ MG(S) (resp.
x ∈M t

G(S)), x ∈M for some M ∈ XI(G), and put

η(G) = min{|MG(S)| : S is an γit-set of G}, and

ηt(G) = min{|M t
G(S)| : S is a γitt-set of G}.



D. Sevilleno, F. Jamil / Eur. J. Pure Appl. Math, 149-163 161

Corollary 5. For all nontrivial connected graphs G and positive integers p ≥ 2,

γit(G[Kp]) ≤ (p− 1)η(G) + γit(G),

and
γitt(G[Kp]) ≤ (p− 1)ηt(G) + γitt(G).

Equality in each is attained if XI(G) consists of pairwise disjoint β0-sets of G.

Proof. Let S ⊆ V (G) be a γit-set of G for which |MG(S)| = η(G), and let y ∈ V (Kp).
Define

C = [∪x∈MG(S) ({x} × V (Kp))] ∪ [∪x∈S\MG(S){(x, y)}].

By Proposition 5, C is an ITD-set of G[Kp]. Consequently,

γit(G[Kp]) ≤ |C| = p · η(G) + (γit(G)− η(G)) = (p− 1)η(G) + γit(G).

Now suppose that XI(G) consists of pairwise disjoint β0-sets of G. Then |MG(S)| =
η(G) = xi(G) for all ITD-sets S of G. Let C = ∪x∈S ({x} × Sx}) be a γit-set of G[Kp].
In view of Proposition 5, S is an ITD-set of G. Write

C =
(
∪x∈MG(S) ({x} × Sx)

)
∪
(
∪x∈S\MG(S) ({x} × Sx)

)
,

and we claim that Sx = V (Kp) for all x ∈ MG(S). Let x ∈ MG(S), and let y ∈ V (Kp).
Pick a β0-set A ⊆ V (G) of G for which x ∈ S ∩ A. By Proposition 5(ii), since {y} is a
β0-set of Kp, there exists u ∈ S∩A, consequently u ∈MG(S), such that Su = {y}. By the
minimality of the cardinality of MG(S), x = u so that y ∈ Sx. Accordingly, Sx = V (Kp).
Thus,

γit(G ◦Kp) = |C| ≥ p · η(G) + (|S| − η(G)) ≥ (p− 1)η(G) + γit(G).

Similar arguments will prove the desired results for γitt(G ◦Kp).

If, in particular, G = K1,n on n+ 1 vertices, then η(G) = 1, γit(G) = γitt(G) = 2, and
γit(G[Kp]) = γitt(G[Kp]) = p+ 1.

Acknowledgements

The authors would like to thank the referees for reviewing the initial paper and for
the invaluable comments and suggestions that eventually led to this much improved ver-
sion of the work. This research is funded by the Department of Science and Technology
- Accelerated Science and Technology Human Resource Development Program (DOST-
ASTHRDP), Philippines.



REFERENCES 162

References

[1] C. Berge. Theory of Graphs and its Applications. Methuen, London, 1962.

[2] J.A. Bondy and Geng hau Fan. A sufficient condition for dominating cycles. Discrete
Math, 67(2):205–208, 1987.

[3] C. Brausee, K. Ozekie M. A. Henning, I. Schiermeyere, and E. Vumar. On upper
bounds for the independent transversal domination number. Discrete Applied Math-
ematics, 236:66–72, 2018.

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

[5] S.R. Canoy and C.E. Go. Domination in the corona and join of Graphs. International
Mathematical Forum, 6(16):763–771, 2011.

[6] E. Cockayne, R.M. Dawes, and S.T. Hedetniemi. Total domination in graphs. Net-
works, 10(3):211–219, 2006.

[7] E.J. Cockayne and S.T. Hedetniemi. Towards a Theory of Domination in Graphs.
Networks, 7(3):247–261, 1997.

[8] W.J. Desormeauxe, T.W. Haynes, and M.A. Henning. An extremal problem for total
domination stable graphs upon edge removal. Discrete Appl. Math, 159:1048–1052,
2011.

[9] Allan Frendrupe, Michael A. Henningbe, Bert Randerathe, and Preben Dahl Vester-
gaard. An upper bound on the domination number of a graph with minimum degree
2. Discrete Mathematics, 309:639–646, 2009.

[10] I.S. Hamid. Independent transversal domination in graphs. Discussiones Mathemat-
icae, Graph Theory, 32:5–17, 2012.

[11] T.W. Haynese, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in
Graphs. Marcel Dekker, Inc., New York, 1998.

[12] M. Henning and A. Yeo. Total domination in graphs. Springer, New York, 2013.

[13] Min-Jen Jou and G. J. Chang. The number of maximum independent sets in graphs.
Taiwanese Journal of Mathematics, 4(4):685–695, 2000.

[14] R.P. Malalay and F.P. Jamil. On disjunctive domination in graphs. Quaestiones
Mathematicae, 43(2):149–168, 2020.

[15] E. Maravillae, R.T. Isla, and S.R. Canoy Jr. Fair Domination in the Join, Corona
and Composition of Graphs. Applied Mathematical Sciences, 8(93):4609–4620.



REFERENCES 163

[16] S.L.N. Marohombsar and F.P. Jamil. On 2-point set dominating sets in graphs.
Advances and Applications in Discrete Mathematics, 21(2):139–162, 2019.

[17] A.Cabrera Martineze, J.M. Sigarreta Almira, and I.G. Yero. On the independence
transversal total domination number of graphs. Discrete Aplied Mathematics, 219:65–
73, 2017.

[18] A.Cabrera Martineze, I. Peterine, and I.G. Yero. Independent Transversal total dom-
ination versus total domination in trees. Discussiones Mathematicae Graph Theory,
41:213–224, 2021.

[19] O. Ore. Theory of Graphs. Amer. Math. Soc., Prividence, RI, 38:206–212, 1962.

[20] V. Samodivkine, H.A. Ahanger, and I.G. Yero. Independent transversal dominating
sets in graphs: complexity and structural properties. Filomat, 30(2):293–303, 2016.