EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 13, No. 4, 2020, 779-793 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global On Semitotal k-Fair and Independent k-Fair Domination in Graphs Marivir M. Ortega1,∗, Rowena T. Isla1,2 1 Department of Mathematics and Statistics, College of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Center for Graph Theory, Algebra, and Analysis, Premier Research Institute of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. In this paper, we introduce and investigate the concepts of semitotal k-fair domination and independent k-fair domination, where k is a positive integer. We also characterize the semitotal 1-fair dominating sets and independent k-fair dominating sets in the join, corona, lexicographic product, and Cartesian product of graphs and determine the exact value or sharp bounds of the corresponding semitotal 1-fair domination number and independent k-fair domination number. 2020 Mathematics Subject Classifications: 05C69, 05C76 Key Words and Phrases: Semitotal domination, Independent domination, k-Fair domination, Join, Corona, Lexicographic product, Cartesian product 1. Introduction Let G = (V (G), E(G)) be a simple graph and v ∈ V (G). The open neighborhood of v in G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} and the closed neighborhood of v is the set NG[v] = NG(v) ∪ {v}. For X ⊆ V (G), the open neighborhood of X in G is the set NG(X) = N(X) = ⋃ v∈X NG(v) and its closed neighborhood is the the set NG[X] = N [X] = N(X) ∪ X. A set D ⊆ V (G) is a dominating set in G if for every v ∈ V (G) \ D, there exists u ∈ D such that uv ∈ E(G), that is, N [D] = V (G). The minimum cardinality of a dominating set in G, denoted by γ(G), is the domination number of G. Any dominating set in G of cardinality γ(G) is referred to as γ-set in G. The theory of independent domination was formalized by Berge [1] and Ore [9] in 1962. The independent domination number and the notation i(G) were introduced by Cockayne and Hedetnieme [2]. Let G be a connected graph. A dominating set S in G is ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v13i4.3812 Email addresses: marivir.ortega@g.msuiit.edu.ph (M. Ortega), rowena.isla@g.msuiit.edu.ph (R.Isla) https://www.ejpam.com 779 c© 2020 EJPAM All rights reserved. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 780 an independent dominating set of G if no two vertices in S are adjacent, that is, S is an independent set. The independent domination number i(G) of a graph G is the minimum cardinality of an independent dominating set. A domination parameter called fair domination was introduced by Caro, Hansberg, and Henning [4] in 2012. For an integer k ≥ 1, a k-fair dominating set (kfd-set) is a dominating set S ⊆ V (G) such that |N(u) ∩ S| = k for every u ∈ V (G)\S. The k-fair domination number of G, denoted by γkfd(G), is the minimum cardinality of a kfd-set. Clearly, k ≤ γkfd(G) ≤ |V (G)|. In 2014, Maravilla, Isla, and Canoy [6] characterized the k-fair dominating sets in the join, corona, lexicographic product, and Cartesian product of graphs and determined the bounds or exact values of the k-fair domination numbers of these graphs. Two variants of k-fair domination, namely connected k-fair domination and neighborhood connected k-fair domination, were studied by Bent-Usman, Gomisong, and Isla [3] in 2018 and by Bent-Usman, Isla, and Canoy [7] in 2019, respectively. Another domination parameter is the semitotal domination of graphs introduced by Goddard, Henning, and McPillan [5] in 2014. For a graph G with no isolated vertices, a set S ⊆ V (G) is a semitotal dominating set in G if S is a dominating set in G such that for every x ∈ S there exists y ∈ S \ {x} such that dG(x, y) ≤ 2. In 2019, Aniversario, Canoy, and Jamil [8] characterized the semitotal dominating sets in the join, corona, and lexicographic product of graphs. Let G be a graph without isolated vertices. A set S ⊆ V (G) is a semitotal k-fair dominating set in G, if S is a k-fair dominating set in G and for every x ∈ S, there exists y ∈ S \ {x} such that d(x, y) ≤ 2. The semitotal k-fair domination number of G, denoted by γt2kf (G), is the minimum cardinality of a semitotal k-fair dominating set. A semitotal k-fair dominating set of cardinality γt2kf (G) is called a minimum semitotal k-fair dominating set or a γt2kf -set. Let G be a connected graph. A set S ⊆ V (G) is an independent k-fair dominating set in G if S is a k-fair dominating set in G and if no two vertices in S are adjacent. The independent k-fair domination number of G, denoted by γikf (G), is the minimum cardinality of an independent k-fair dominating set. An independent k-fair dominating set of cardinality γikf (G) is called a minimum independent k-fair dominating set or a γikf -set. The join G + H of two graphs G and 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)}. The corona of two graphs G and H, denoted by G ◦ H, is the graph obtained by taking one copy of G of order n and n copies of H, and then joining the i-th vertex of G to every vertex in the i-th copy of H. For every v ∈ V (G), we denote by Hv the copy of H whose vertices are joined or attached to the vertex v. For each v ∈ V (G), the subgraph 〈v〉+Hv of G ◦ H will be denoted by v + Hv. The lexicographic product of two graphs 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]) satisfying the following conditions: (u1, v1)(u2, v2) ∈ E(G[H]) if and only if either u1u2 ∈ E(G) or u1 = u2 and v1v2 ∈ E(H). The Cartesian product of two graphs M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 781 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) satisfying the following conditions: (u1, v1)(u2, v2) ∈ E(G�H) if and only if either u1u2 ∈ E(G) and v1 = v2 or u1 = u2 and v1v2 ∈ E(H). 2. Preliminary Results Remark 1. Any semitotal kfd-set is a kfd-set, where k is a positive integer. Theorem 1. Let G be a nontrivial connected graph. Then γt21f (G) = 2 if and only if there exist adjacent vertices a and b such that NG(a) ∩ NG(b) = ∅ and V (G) \ NG[a] = NG(b) \ {a}. Proof. Suppose γt21f (G) = 2. Let S = {a, b} be a γt21f -set of G. Since S is a 1fd-set, no vertex v ∈ V (G) \S with v ∈ NG(a)∩NG(b) exists, i.e., NG(a)∩NG(b) = ∅. This implies that ab ∈ E(G) because S is a semitotal dominating set. Moreover, V (G) \ NG[a] = NG(b) \ {a} (or V (G) \NG[b] = NG(a) \ {b}) because S is a dominating set. The converse is clear. � Corollary 1. γt21f (K2) = γt21f (K1 + (K1 ∪H)) = γt21f (K2 ◦H) = 2 for any graph H. Lemma 1. [6] Let G be a connected graph of order n ≥ 1 and let k be a positive integer such that k ≤ n. Then: (i) k ≤ γkfd(G) ≤ n. (ii) γkfd(G) = k if and only if G has a kfd-set S with |S| = k. (iii) If γkfd(G) = n, then G has no vertex of degree k. Theorem 2. Let G be a connected graph of order n ≥ 2 and let k be a positive integer with 2 ≤ k ≤ n. Then γt2kf (G) = k if and only if n = k or G = H1 + H2 for some graphs H1 and H2 with |V (H1)| = k. Proof. Suppose γt2kf (G) = k. Suppose further that k < n. Let S be a γt2kf -set of G. Then |S| = k. Set H1 = 〈S〉 and H2 = 〈V (G) \ S〉. Since S is a k-fair dominating set of G, it follows that V (G) \ S ⊆ NG(v) for each v ∈ S. Hence, G = H1 +H2. For the converse, suppose that G = H1 + H2 where |V (H1)| = k. Then clearly, S = V (H1) is a k-fair dominating set of G. Let x, y ∈ S with x 6= y. Suppose xy /∈ E(G). Pick any z ∈ V (H2). Then z ∈ NG(x) ∩ NG(y). This implies that dG(x, y) = 2. Therefore, S is a semitotal kfd-set of G. By Lemma 1 (ii), S is a γt2kf -set of G, that is, γt2kf (G) = |S| = k. � Corollary 2. Let G be a connected graph of order n ≥ 3. Then γt22f (G) = 2 if and only if G = K2 +H or G = K2 +H for some graph H. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 782 Proof. Suppose γt22f (G) = 2, say S = {a, b} is a γt22f -set ofG. LetH = 〈V (G) \ S〉. Since S is a 2-fair dominating set, V (H) = V (G) \ S ⊆ NG(a) ∩NG(b). Since S is a semitotal 2-fair dominating set, either ab ∈ E(G) or dG(a, b) = 2. Thus, G = K2+H or G = K2+H. For the converse, suppose G = K2 +H or G = K2 +H. Then clearly, γt22f (G) = 2. � Theorem 3. Let G be a connected graph of order n ≥ 2 and let k ≥ 2. Then S ⊆ V (G) is a semitotal kfd-set if and only if it is a kfd-set. In particular, γt2kf (G) = γkfd(G). Proof. Suppose S is a semitotal kfd-set. Then S is a kfd-set by Remark 1. For the converse, suppose S is a kfd-set. Let x ∈ S. If NG(x) ∩ S 6= ∅, then there exists w ∈ S such that dG(x,w) = 1. Suppose NG(x) ∩ S = ∅. Let v ∈ NG(x). Then v ∈ V (G) \ S. Since S is a kfd-set and k ≥ 2, there exists u ∈ S \ {x} such that uv ∈ E(G). Hence, dG(x, u) = 2. Thus, dG(x, z) ≤ 2 for some z ∈ S. Therefore, S is a semitotal kfd-set of G. Accordingly, γt2kf (G) = γkfd(G). � Remark 2. Not every connected graph of order n admits an independent kfd-set, where k is a positive integer and 1 ≤ k ≤ α(G), where α(G) is the independence number of G. To see this, consider C4. γ1fd(C4) = 2 but C4 has no independent 1fd-set. Theorem 4. Let G be a connected graph of order n and let k be a positive integer with 1 ≤ k ≤ α(G). Then G admits an independent kfd-set (and hence, γikf (G) = k) if and only if G = Kk +H for some graph H. Proof. Suppose G admits an independent kfd-set, say S = {a1, a2, ..., ak}. Let H = 〈V (G) \ S〉. Since S is a kfd-set, V (H) = V (G) \ S ⊆ NG(ai) ∩ NG(aj) for all i, j = 1, 2, ..., k and i 6= j. Since S is an independent kfd-set of G, |NG(S) ∩ S| = ∅. Thus, G = Kk +H. For the converse, suppose G = Kk + H for some graph H. Then clearly, S = V (Kk) is an independent kfd-set of G and γikf (G) = k. � Theorem 5. Let G be a connected graph and suppose G admits an independent 1fd-set. Then 1 ≤ γi1f (G) ≤ α(G). Moreover, (i) γi1f (G) = 1 if and only if G = K1 +H for some graph H, and (ii) γi1f (G) = α(G) ≥ 2 if and only if G has a maximum independent set such that dG(x, y) ≥ 3 for each pair of vertices x, y ∈ S with x 6= y, and no other independent set satisfies this property. Proof. Let S be a γi1f -set. Since S is an independent set, 1 ≤ |S| = γi1f (G) ≤ α(G). (i) is an immediate consequence of Theorem 4. (ii) Suppose γi1f (G) = α(G) ≥ 2. Let S be a γi1f -set of G. Then S is a maximum independent set of G. Let x, y ∈ S with x 6= y. Since S is an independent 1fd-set, dG(x, y) ≥ 3. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 783 For the converse, suppose thatG has a maximum independent set S such that dG(x, y) ≥ 3 for all x, y ∈ S with x 6= y, and that no other independent set satisfies this property. Then S is a dominating set of G. Let z ∈ V (G) \ S. Then there exists v ∈ S ∩ NG(z). Since dG(v, y) ≥ 3 for all y ∈ S \ {v}, NG(z) ∩ S = 1. Thus, S is an independent 1fd-set of G. Hence, γi1f (G) ≤ |S| = α(G). By the additional property, γi1f (G) = α(G). � Since Kn = K1 +Kn−1 and α(Kn) = 1, the next result immediately follows. Corollary 3. For any positive integer n ≥ 1, γi1f (Kn) = 1. Remark 3. Any independent kfd-set is a kfd-set, where k is a positive integer. Theorem 6. Let G be a connected graph with |V (G)| ≥ 4 and suppose G admits an independent 1fd-set. Then γi1f (G) = 2 if and only if there exist non-adjacent vertices a and b of G satisfying the following conditions: (i) NG[a] ∪NG[b] = V (G) (ii) NG[a] ∩NG[b] = ∅ Proof. Suppose S = {a, b} is a γi1f -set of G. Since S is a dominating set, Condition (i) holds. Suppose there exists y ∈ NG[a]∩NG[b]. Then dG(a, b) = 2, contrary to the fact that dG(a, b) ≥ 3 since S is an independent 1fd-set. Thus, Condition (ii) holds. For the converse, suppose that S = {a, b} satisfies Conditions (i) and (ii). Then clearly, γi1f (G) = 2. � Theorem 7. For any positive integer n ≥ 1, γi1f (Pn) = dn3 e. Proof. Let Pn = {v1, v2, v3, ..., vn}. Clearly, γi1f (P1) = γi1f (P2) = γi1f (P3) = 1. Let n > 3 and consider the following cases: Case 1: n = 3r Group the first 3r vertices of Pn into r disjoint subsets S1 = {v1, v2, v3, } S2 = {v4, v5, v6} ... Sr−1 = {v3r−5, v3r−4, v3r−3} Sr = {v3r−2, v3r−1, v3r}. For every induced subgraph 〈vi, vi+1, vi+2〉 of Pn, where i = 1, 4, ..., 3r−2, the vertices vi+1 form an independent 1-fair dominating set of Pn. Thus, the set T = {v2, v5, ..., v3r−4, v3r−1} is an independent 1-fair dominating set of Pn. Since |T | = r, γi1f (Pn) ≤ r. Note that every three adjacent vertices in Pn can be dominated by a single vertex. Thus, every independent 1-fair dominating set of Pn contains at least dn3 e vertices. Hence, γi1f (Pn) ≥ dn3 e = r. Thus, γi1f (Pn) = dn3 e. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 784 Case 2: n = 3r + 2 In Case 1, the set T is a γi1f -set of the induced subgraph 〈v1, v2, ..., v3r〉 of Pn. Since n = 3r+ 2, the set T ∪ {v3r+2} is a γi1f -set of Pn. Thus, γi1f (Pn) = r+ 1 = ⌈ 3r+2 3 ⌉ = dn3 e. Case 3: n = 3r + 1 Consider the grouping of the first 3r vertices of Pn given in Case 1. The set S = {v1, v4, ..., v3r−2}∪{v3r+1} is an independent 1-fair dominating set of Pn. Thus, γi1f (Pn) ≤ |S| + 1 = r + 1 = ⌈ 3r+1 3 ⌉ = dn3 e. Note that each of the first r − 1 induced subgraph 〈vi, vi+1, vi+2〉 can be dominated by a single vertex, while the induced subgraph 〈v3r−2, v3r−1, v3r, v3r+1〉 can be dominated by the vertices v3r−2 and v3r+1. Thus, every independent 1-fair dominating set of Pn contains at least (r − 1) + 2 = r + 1 = ⌈ 3r+1 3 ⌉ = dn3 e vertices. Hence, γi1f (Pn) ≥ dn3 e. Therefore, γi1f (Pn) = dn3 e. � Corollary 4. For any positive integer n ≡ 0 (mod 3), γi1f (Cn) = n 3 . Proof. Immediately follows from Case 1 of Theorem 7. � The following results are used in the succeeding sections. Theorem 8. [6] Let G and H be nontrivial connected graphs of orders m and n, respectively, and k a positive integer with 1 ≤ k ≤ max{m,n}. Then S ⊆ V (G + H) is a kfd-set in G+H if and only if one of the following holds: (a) S = V (G+H). (b) S ⊆ V (G), |S| = k and S is a kfd-set in G. (c) S ⊆ V (H), |S| = k and S is a kfd-set in H. (d) S = SG ∪ SH , where SG is a (k − |SH |)fd-set in G and SH is a (k − |SG|)fd-set in H. (e) S = V (G) ∪ T , where |V (G)| = m < k and T is a (k −m)fd-set in H. (f) S = D ∪ V (H), where |V (H)| = n < k and D is a (k − n)fd-set in G. Theorem 9. [6] Let G and H be nontrivial connected graphs and let k be a positive integer with k ≤ |V (H)|. Then C ⊆ V (G ◦H) is a kfd-set in G ◦H if and only if one of the following holds: (a) C = V (G) ∪B, where B = ∅ or B = ⋃ v∈V (G) Sv, where each Sv is a (k − 1)fd-set in Hv. (b) C = ⋃ v∈V (G) Sv, where each Sv is a kfd-set in Hv and |Sv| = k. Theorem 10. [6] Let G and H be nontrivial connected graphs. Then C = ⋃ x∈S ({x}×Tx) ⊆ V (G[H]) is a kfd-set in G[H] if and only if the following hold: M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 785 (i) S is a dominating set in G. (ii) For each x ∈ S ∩NG(S), Tx = V (H) and |V (H)| = r ≤ k whenever C 6= V (G[H]) or Tx is an rfd-set and ∑ z∈NG(x)∩S |Tz| = k − r. (iii) For each x ∈ S\NG(S), Tx = V (H) and |V (H)| ≤ k or |Tx| = k and Tx is a kfd-set in H. (iv) For each y ∈ V (G)\S, ∑ v∈NG(y)∩S |Tv| = k. Corollary 5. [6] Let G and H be nontrivial connected graphs. Then C = ⋃ x∈S ({x}×Tx) ⊆ V (G[H]) is a 1fd-set in G[H] if and only if S is a 1fd-set in G, S ∩NG(S) = ∅, Tx is a dominating set of H, and |Tx| = 1 for each x ∈ S. Theorem 11. [6] Let G and H be nontrivial connected graphs of orders m and n, respectively, and k a positive integer with 1 ≤ k ≤ min{m,n}. Then C = ⋃ x∈V (G) [{x} × Tx] ⊆ V (G�H) is a kfd-set in G�H if and only if (i) V (H)\Tx ⊆ NH(Tx) ∪ ( ⋃ z∈NG(x) Tz) for each x ∈ V (G), and (ii) For each x ∈ V (G), Tx = V (H) or for each a ∈ V (H)\Tx, either |NH(a) ∩ Tx| = k and |{z : z ∈ NG(x), a ∈ Tz}| = 0 or |NH(a) ∩ Tx| = r < k and a ∈ ⋂k−r i=1 Txi, where xi ∈ NG(x) for i = 1, 2, ..., k − r . Corollary 6. [6] Let G and H be nontrivial connected graphs of orders m and n, respectively, and k a positive integer with k ≤ min{m,n}. Then γkfd(G�H) ≤ min{n · γkfd(G),m · γkfd(H)}. 3. Semitotal 1-Fair Domination In view of Theorem 3, which shows that the concept of semitotal k-fair dominatioin coincides with the notion of k-fair domination when k ≥ 2, this section investigates semitotal k-fair domination in graphs only for k = 1. The following remark is an immediate consequence of Remark 1 for k = 1. Remark 4. For any connected graph G of order n ≥ 2, γ1fd(G) ≤ γt21f (G) and γt21f (G) ≥ 2. The succeeding two results are easy to verify. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 786 Proposition 1. Let n and r be positive integers where n ≥ 2 and r ≥ 1. Then γt21f (Pn) =  2, 2 ≤ n ≤ 4 2r, n = 4r 2r + 1, n = 4r + 1 2r + 2, n = 4r + 2, 4r + 3. Proposition 2. Let n and r be positive integers where n ≥ 3 and r ≥ 1. Then γt21f (Cn) =  3, n = 3 2r, n = 4r 2r + 1, n = 4r + 1 2r + 2, n = 4r + 2 2r + 3, n = 4r + 3. Theorem 12. Let a and b be positive integers such that 2 ≤ a ≤ b. Then there exists a connected graph G such that γ1fd(G) = a and γt21f (G) = b. Proof. Consider the following cases: Case 1. a = b Let G = G1 be the graph shown in Figure 1. ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... • • • • • •· · · x1 x2 x3 x4 xa−1 xa Figure 1: A graph G with γ1fd(G) = a = γt2 1f (G) = b It is clear that the set A = {x1, x2, ..., xa−1, xa} is both a γ1fd-set and a γt21f - set in G1. It follows that γ1fd(G) = a = γt21f (G) = b. Case 2. a < b Let G = G2 be the graph shown in Figure 2. • • • • • xa−1 v xa x1 x2 x3 · · ·................................................................................................................ ................................................................................................................ .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .......................................................................................... .................................... ................... .................. .................. .................. .................. .................. ......... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................... ............................................................................................. .................................... ............ ........... ........... ........... ........... ........... .... .................................... .................................................................................................................................................................................... .................................... ......... ........ ........ ........ ........ ...... .................................... .................................................................................................................................................................................................................................................................................................. .................................... ...................................................................................................................... .................................... .................................... · · ·• • • • y1 y2 y3 yb−a Figure 2: A graph G with γ1fd(G) = a < γt2 1f (G) = b Let A = {x1, x2, ..., xa}. It is clear that the set A is a γ1fd-set and the set B = (A \ {xa}) ∪ {v} ∪ {y1, y2, y3, ..., yb−a} is a γt21f -set in G. It follows that γ1fd(G) = |A| = a and γt21f (G) = |B| = (a− 1) + 1 + (b− a) = b. � M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 787 Corollary 7. γt21f − γ1fd can be made arbitrarily large. We now characterize the semitotal 1-fair dominating sets in the join, corona, lexicograph- ic product, and Cartesian product of graphs in this section. We also establish the exact value or sharp bounds of the corresponding semitotal 1-fair domination number. Theorem 13. Let G and H be any two graphs of orders m and n, respectively. A set C ⊆ V (G+H) is a semitotal 1fd-set of G+H if and only if C = V (G+H) or C = {v, w} for some isolated vertices v and w of G and H, respectively. Proof. Immediately follows from γt21f (G+H) ≥ 2 and Theorem 8. � Corollary 8. Let G and H be any graphs of orders m and n, respectively. Then γt21f (G+ H) = 2 if G and H both contain isolated vertices and γt21f (G+H) = m+ n otherwise. Theorem 14. Let G be a nontrivial connected graph and H be any graph. Then C ⊆ V (G ◦H) is a semitotal 1fd-set in G ◦H if and only if C = V (G) or C = V (G ◦H). Proof. Suppose C ⊆ V (G ◦H) is a semitotal 1fd-set in G ◦H. Then C is a 1fd-set in G ◦H. It now follows by Theorem 9 that C = V (G) or C = V (G ◦H). The converse is obvious. � Corollary 9. Let G be a nontrivial connected graph and H be any graph. Then γt21f (G ◦H) = |V (G)|. Theorem 15. Let G and H be nontrivial connected graphs. A set C ⊆ V (G[H]) is a semitotal 1fd-set of G[H] if and only if C = V (G[H]). Proof. Suppose C = ⋃ x∈S ({x} × Tx) is a semitotal 1fd-set of G[H]. Then S is a 1fd-set of G, S ∩ NG(S) = ∅, Tx is a dominating set of H, and |Tx| = 1 for each x ∈ S, by Corollary 5. Suppose C 6= V (G[H]), say there exists (y, a) ∈ V (G[H]) \ C. If y /∈ S, then |NG(y) ∩ S| = 1 because S is a 1fd-set of G. Let NG(y) ∩ S = {z} and let Tz = {b}. Since C is a semitotal 1fd-set of G[H], there exists (w, c) ∈ C such that dG[H]((z, b), (w, c)) ≤ 2. Now, since S ∩ NG(S) = ∅ and w ∈ S \ {z}, it follows that dG(z, w) = 2 (that is, dG[H]((z, b), (w, c)) = 2). Let u ∈ NG(z) ∩ NG(w). Then u ∈ V (G) \ S. Since z, w ∈ NG(u) ∩ S, S is not a 1fd-set, a contradiction. Suppose y ∈ S. Then |Ty| = 1. Again, since C is a semitotal 1fd-set of G[H], S ∩NG(S) = ∅, and |Ty| = 1, there exists p ∈ NG(y)∩ S such that dG(y, p) = 2. This implies that there exists q ∈ V (G) \ S (q ∈ NG(y) ∩NG(p)) such that |NG(q) ∩ S| ≥ 2, contrary to the fact that S is a 1fd-set of G. Thus, C = V (G[H]). The converse is clear. � Corollary 10. Let G and H be nontrivial connected graphs of orders m and n, respectively. Then γt21f (G[H]) = m · n. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 788 Theorem 16. Let G and H be nontrivial connected graphs. Then C = ⋃ x∈V (G) [{x}×Tx] ⊆ V (G�H) is a semitotal 1fd-set of G�H if and only if: (i) V (H)\Tx ⊆ NH(Tx) ∪ ( ⋃ z∈NG(x) Tz) for each x ∈ V (G); (ii) for each x ∈ V (G), Tx = V (H) or for each a ∈ V (H)\Tx, either |NH(a)∩Tx| = 1 and {z : z ∈ NG(x), a ∈ Tx} = ∅, or NH(a) ∩ Tx = ∅ and a ∈ Ty for exactly one y ∈ NG(x); and (iii) for each x ∈ V (G) and for each a ∈ Tx, there exists b ∈ Tx such that ab ∈ E(H) or there exists y ∈ NG(x) such that a ∈ Ty. Proof. Suppose C = ⋃ x∈V (G) [{x} × Tx] ⊆ V (G�H) is a semitotal 1fd-set in G�H. Since C is a 1fd-set in G�H, Conditions (i) and (ii) hold by Theorem 11. Let x ∈ V (G). Suppose there exists a ∈ Tx such that for all b ∈ Tx, ab /∈ E(H) and for all y ∈ NG(x), a /∈ Ty. Since C is a semitotal dominating set, there exists (x, c) ∈ C such that dG�H ((x, a), (x, c)) = 2 or there exists (z, a) ∈ C such that dG�H ((x, a), (z, a)) = 2 or there exist y ∈ NG(x) and b ∈ Ty such that dG�H ((x, a), (y, b)) = 2, where (y, b) ∈ C. However, in each of these cases, there exists (w, d) ∈ V (G�H)\C such that |NG�H(w, d)∩ C| ≥ 2, contrary to the assumption that C is a 1fd-set. Hence, Condition (iii) must be satisfied. For the converse, suppose Conditions (i), (ii), and (iii) hold. By Theorem 11, (i) and (ii) imply that C is a 1fd-set in G�H, while (iii) implies that C is a semitotal dominating set. Thus, C is a semitotal 1fd-set in G�H. � Corollary 11. Let G and H be nontrivial connected graphs. Then C1 = S1 × V (H) and C2 = V (G)× S2 are semitotal 1fd-sets in G�H if and only if S1 and S2 are 1fd-sets in G and H, respectively. The following result is an immediate consequence of Corollary 11. Corollary 12. Let G and H be nontrivial connected graphs. Then γt21f (G�H) ≤ min{|V (H)| · γ1fd(G), |V (G)| · γ1fd(H)}. Remark 5. The bound given in Corollary 12 is sharp. To see this, consider the graph shown in Figure 3. The shaded vertices in P4�P6 form a γt21f -set. Thus, γt21f (P4�P6) = 8 = min{6 · 2, 4 · 2} = min{|V (P6)| · γ1fd(P4), |V (P4)| · γ1fd(P6)} = |V (P4)| · γ1fd(P6). M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 789 ................................................................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... ................................................................................... .................................... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... • • • • • • • • Figure 3: The graph P4�P6, with γ t2 1f (P4�P6) = 8. 4. Independent k-Fair Domination We characterize the independent k-fair dominating sets in the join, corona, lexicographic product, and Cartesian product of graphs in this section. We also determine the exact value or sharp bounds of the corresponding independent k-fair domination number. Theorem 17. Let G and H be nontrivial connected graphs of orders m and n, respectively, and k a positive integer with 1 ≤ k ≤ max{dm2 e, d n 2 e}. Then G+H admits an independent kfd-set if and only if G or H admits an independent kfd-set. Moreover, S ( V (G+H) is an independent kfd-set in G+H if and only if one of the following holds: (i) S ( V (G), |S| = k and S is an independent kfd-set in G. (ii) S ( V (H), |S| = k and S is an independent kfd-set in H. Proof. Suppose G+H admits an independent kfd-set, where 1 ≤ k ≤ max{dm2 e, d n 2 e}. Suppose further that S ( V (G + H) is an independent kfd-set in G + H. If there exist u, x ∈ S such that u ∈ V (G) and x ∈ V (H), then ux ∈ E(G + H), contrary to the assumption that S is an independent set in G+H. Hence, either S ( V (G) or S ( V (H). Assume that S ( V (G). Let x ∈ V (H). Then |NG+H(x) ∩ S| = |S| = k. Since S is a kfd-set of G + H, |NG(v) ∩ S| = |NG+H(v) ∩ S| = k for every v ∈ V (G) \ S. Hence, S is a kfd-set in G. Since S is an independent set by assumption, Statement (i) holds. Similarly, if S ( V (H), then S is an independent kfd-set in H, showing that Statement (ii) holds. Therefore, G or H admits an independent kfd-set. Conversely, suppose that Statement (i) or (ii) holds. Assume that Statement (i) is true. Then |NG+H(v) ∩ S| = |NG(v) ∩ S| = k for each v ∈ V (G) \ S. Moreover, |NG+H(x) ∩ S| = |S| = k for every vertex x ∈ V (H). Thus. S is a kfd-set in G + H. Therefore, S ( V (G + H) is an independent kfd-set in G + H. The same conclusion similarly follows if Statement (ii) holds. � The next result is an immediate consequence of Theorem 17. Corollary 13. Let G and H be connected nontrivial graphs of orders m and n, respectively, and k a positive integer with 1 ≤ k ≤ max{dm2 e, d n 2 e}. If G or H has an independent kfd-set S with |S| = k, then γikf (G+H) = k. Theorem 18. Let G and H be nontrivial connected graphs, and let k be a positive integer with k ≤ ⌈ |V (H)| 2 ⌉ . Then G ◦ H admits an independent kfd-set if and only if H admits an independent kfd-set consisting of k vertices. M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 790 Proof. Suppose G ◦H admits an independent kfd-set, where k ≤ ⌈ |V (H)| 2 ⌉ . Suppose further that C ( V (G ◦H) is an independent kfd-set in G ◦H. Suppose C ∩ V (G) 6= ∅, say v ∈ C ∩V (G). Since C is an independent set, V (Hv)∩C = ∅ and |NG◦H(x)∩C| = 1 for all x ∈ V (Hv). This implies that k = 1. Now let w ∈ NG(v). Then w /∈ C. Since |NG◦H(w) ∩ C| = 1, V (Hw) ∩ C = ∅. Hence, V (Hw) ∩ NG◦H [C] = ∅, a contradiction (since C is a dominating set). Thus, C ∩ V (G) = ∅. Then by Theorem 9, C = ⋃ v∈V (G) Sv, where each Sv is an independent kfd-set in Hv and |Sv| = k for each v ∈ V (G). Therefore, H admits an independent kfd-set consisting of k vertices. Conversely, suppose H admits an independent kfd-set consisting of k vertices. Let C = ⋃ v∈V (G) Sv, where each Sv is an independent kfd-set in Hv and |Sv| = k. Then C is an independent kfd-set in G ◦H by Theorem 9. � The next result is an immediate consequence of Theorem 18. Corollary 14. Let G and H be nontrivial connected graphs of orders m and n, respectively, and let k be a positive integer with k ≤ ⌈ n 2 ⌉ . If H has an independent kfd-set S with |S| = k, then γikf (G ◦H) = mk. Theorem 19. Let G and H be nontrivial connected graphs and let k be a positive integer with 1 ≤ k ≤ ⌈ |V (H)| 2 ⌉ . If G[H] admits an independent kfd-set, then C = ⋃ x∈S ({x}×Tx) ( V (G[H]) is an independent kfd-set in G[H] if and only if the following hold: (i) S is an independent 1fd-set in G, (ii) for each x ∈ S, |Tx| = k and Tx is an independent kfd-set in H. Proof. Suppose C = ⋃ x∈S ({x} × Tx) ( V (G[H]) is an independent kfd-set in G[H]. Then C is a kfd-set in G[H] and by Theorem 10, S is a dominating set in G. Moreover, since C is an independent set, S∩NG(S) = ∅. Finally, from Statement (iv) of Theorem 10, for each y ∈ V (G)\S, ∑ v∈NG(y)∩S |Tv| = k, hence |NG(y)∩S| = 1. Thus, S is an independent 1fd-set in G and Statement (i) holds. Furthermore, for each x ∈ (S\NG(S)) = S, |Tx| = k and Tx is a kfd-set in H by Statement (iii) of Theorem 10, where k ≤ ⌈ |V (H)| 2 ⌉ since C is an independent set. Suppose there is a vertex a ∈ Tx which is adjacent to a vertex b ∈ Tx. Then (x, a) is adjacent to (x, b) in C, contrary to assumption. Hence, Tx is an independent kfd-set in H and Statement (ii) holds. Conversely, suppose Statements (i) and (ii) hold. Then Tx is a kfd-set in H for each x ∈ S, and ∑ v∈NG(y)∩S |Tv| = k for each y ∈ V (G)\S. Thus, C is a kfd-set in G[H] by Theorem 10. Let (x, a) ∈ C. Then x ∈ S and a ∈ Tx. Suppose there exists (x, b) ∈ C such that (x, a)(x, b) ∈ E(G[H]). Then b ∈ Tx and ab ∈ E(H), contrary to Statement (ii) that M. Ortega, R. Isla / Eur. J. Pure Appl. Math, 13 (4) (2020), 779-793 791 Tx is an independent set. Hence, (x, a) is not adjacent to any (x, b) ∈ C. Next, suppose there exists (y, d) ∈ C, y 6= x, such that (x, a)(y, d) ∈ E(G[H]). Then y ∈ NG(x) ∩ S, contrary to the fact that S ∩NG(S) = ∅. Hence, (x, a) is not adjacent to any (y, d) ∈ C. Therefore, C is an independent kfd-set in G[H]. � Corollary 15. Let G and H be nontrivial connected graphs with γikf (H) = k ≤ ⌈ |V (H)| 2 ⌉ . If G[H] admits an independent kfd-set, then γikf (G[H]) = k · γi1f (G). Proof. Let S be a γi1f -set of G and let {a1, ..., ak} be a γikf -set of H. Let Tx = {a1, ..., ak} for each x ∈ S. Then C = ⋃ x∈S ({x} × Tx) is an independent kfd-set in G[H] by Theorem 19. Hence, γikf (G[H]) ≤ |C| = k · γi1f (G). Now, let C0 be a γikf -set of G[H]. By Theorem 19, C0 = ⋃ x∈S0 [{x}×Qx], where S0 is an independent 1fd-set and Qx is an independent kfd-set of H with |Qx| = k for each x ∈ S0. Hence, γikf (G[H]) = |C0| = k|S0| ≥ k · γi1f (G). This establishes the desired equality. � Theorem 20. Let G and H be nontrivial connected graphs of orders m and n, respectively, and let k be a positive integer with 1 ≤ k ≤ min{m,n}. If G�H admits an independent kfd-set, then C = ⋃ x∈V (G) ({x} × Tx) ( V (G�H) is an independent kfd-set in G�H if and only if: (i) Tx is an independent set in H for each x ∈ V (G), (ii) for each x ∈ V (G) and each a ∈ Tx, |{z ∈ V (G) : z ∈ NG(x), a ∈ Tz}| = 0, (iii) V (H)\Tx ⊆ NH(Tx) ⋃ ( ⋃ z∈NG(x) Tz) for each x ∈ V (G), and (iv) for each b ∈ V (H) \Tx, either |NH(b)∩Tx| = k and |{z : z ∈ NG(x), b ∈ Tz}| = 0 or |NH(b) ∩ Tx| = r < k and b ∈ k−r⋂ i=1 Txi, where xi ∈ NG(x) for i = 1, 2, ..., k − r. Proof. Suppose C = ⋃ x∈V (G) ({x}×Tx) ( V (G�H) is an independent kfd-set in G�H. Then by Theorem 11, (iii) and (iv) hold. Suppose there is a vertex a ∈ Tx which is adjacent to some vertex b in Tx. Then (x, a) is adjacent to (x, b) in C, contrary to assumption. Hence, Tx is an independent set in H and (i) holds. Finally, suppose there is a vertex a ∈ Tx such that for some vertex z ∈ NG(x), a ∈ Tz. Then (z, a) ∈ C and (x, a) is adjacent to (z, a) in C, contrary to assumption. Hence, (ii) holds. Conversely, suppose (i) to (iv) hold. From (iii) and (iv), C is a kfd-set by Theorem REFERENCES 792 11. By (i) and (ii), C is an independent set in G�H. Thus, C is an independent kfd-set in G�H. � The next result immediately follows from Remark 3 and Corollary 6. Corollary 16. Let G and H be nontrivial connected graphs of orders m and n, respectively, and k a positive integer with 1 ≤ k ≤ min{m,n}. If G�H admits an independent kfd-set, then γikf (G�H) ≤ min{m · γkfd(H), n · γkfd(G)}. Remark 6. The bound given in Corollary 16 is sharp. However, the strict inequality can be attained. To see this, consider the graphs shown in Figure 4. The shaded vertices in each graph form a γikf -set. Thus, γi1f (P2�P3) = 2 = min{2 ·1, 3 ·1} = min{|V (P2)| ·γ1fd(P3), |V (P3)| · γ1fd(P2)} = |V (P2)| · γ1fd(P3) and γi3f (P3�P3) = 5 < min{3 · 3, 3 · 3} = min{|V (P3)| · γ3fd(P3), |V (P3)| · γ3fd(P3)}. ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ ................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ...• • ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ ................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ...•• • • • Figure 4: The graphs P2�P3 and P3�P3 with γi 1f (P2�P3) = 2 and γi 3f (P3�P3) = 5 Acknowledgements This research is funded by the Department of Science and Technology-Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP) and the Mindanao State University-Iligan Institute of Technology. The authors would like to thank the reviewers for their invaluable comments and suggestions that led to this improved version of the paper. References [1] C. Berge. The Theory of Graphs and Applications. Methuen, London, 1962. [2] E. Cockayne and S. Hedetniemi. Independent Graphs. Congr. Numer., X:471–491, 1974. [3] W. Bent-Usman. D. Gomisong and R. Isla. Connected k-Fair Domination in the Join, Corona, Lexicographic and Cartesian Product of Graphs. Applied Mathematical Sciences, 12(27):1341–1355, 2018. REFERENCES 793 [4] Y. Caro. A. Hansberg and M. Henning. Fair Domination in Graphs. Discrete Mathematics, 312(19):2905–2914, 2012. [5] W. Goddard. M. Henning and C. McPillan. Semitotal Domination in Graphs. Utilitas Mathematica, 94:67–81, 2014. [6] E. Maravilla. R. Isla and S. Canoy Jr. k-Fair Domination in the Join, Corona, Composition and Cartesian Product of Graphs. Applied Mathematical Sciences, 8(178):8863–8874, 2014. [7] W. Bent-Usman. R. Isla and S. Canoy Jr. Neighborhood Connected k-Fair Domination Under Some Binary Operations. European Journal of Pure and Applied Mathematics, 12(3):1337–1349, 2019. [8] I. Aniversario. S. Canoy Jr and F. Jamil. On Semitotal Domination in Graphs. European Journal of Pure and Applied Mathematics, 12(4):1410–1425, 2019. [9] O. Ore. Theory of Graphs. Amer. Math. Colloq. Publ., 38:206–212, 1962.