EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 12, No. 3, 2019, 1337-1349 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Neighborhood Connected k-Fair Domination under some Binary Operations Wardah M. Bent-Usman1,∗, Rowena T. Isla2, Sergio R. Canoy, Jr.2 1 Mathematics Department, College of Natural Sciences and Mathematics, Mindanao State University-Main Campus, 9700 Marawi City, Philippines 2 Department of Mathematics and Statistics, College of Science and Mathematics, Cen- ter 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. Let G = (V (G), E(G)) be a simple graph. A neighborhood connected k-fair dominating set (nckfd-set) is a dominating set S ⊆ V (G) such that the |N(u)∩ S| = k for every u ∈ V (G)\S and the induced subgraph 〈N(S)〉 of S is connected. The neighborhood connected k-fair domination number of G, denoted by γnckfd(G), is the minimum cardinality of an nckfd-set. In this paper, we introduce and investigate the notion of neighborhood connected k-fair domination in graphs. We also characterize such dominating sets in the join, corona, lexicographic and Cartesian products of graphs and determine the exact values or sharp bounds of their corresponding neighborhood connected k-fair domination number. 2010 Mathematics Subject Classifications: 05C69, 05C76 Key Words and Phrases: k-fair domination, Neighborhood connected k-fair domination, Join, Corona, Lexicographic product, Cartesian product 1. Introduction Let G = (V (G), E(G)) be a simple graph. A set S ⊆ V (G) is a dominating set in G if for every v ∈ V (G)\S, there exists u ∈ S such that uv ∈ E(G). The minimum cardinality of a dominating set in G, denoted by γ(G) , is the domination number of G. Any dominat- ing set in G of cardinality γ(G) is referred to as a γ-set in G. Arumugam and Sivagnanam [1] introduced a variation of domination called the neighborhood connected domination in graphs. A dominating set S of a connected graph G is called a neighborhood connected dominating set (ncd-set) if the induced subgraph 〈N(S)〉 of the open neighborhood N(S) of S is connected. The minimum cardinality of an ncd-set of G is called the neighborhood ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v12i3.3506 Email addresses: wardah bentusman@yahoo.com (W. Bent-Usman), rowena.isla@g.msuiit.edu.ph (R. Isla), sergio.canoy@g.msuiit.edu.ph (S. Canoy) http://www.ejpam.com 1337 c© 2019 EJPAM All rights reserved. W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1338 connected domination number of G and is denoted by γnc(G). We refer to a minimum ncd-set of G as a γnc-set. Another domination variant is fair domination, introduced by Caro, Hansberg and Henning [3] in 2011. For an integer k ≥ 1, a k-fair dominating set (kfd-set) is a dominat- ing 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. Maravilla, Isla, and Canoy [4–6] and Bent-Usman, Gomisong, and Isla [2] characterized the fair dominating, k-fair dominating, fair total dominating and connected k-fair dom- inating sets in the join, corona, lexicographic product, and Cartesian product of graphs and determined the bounds or exact values of the fair, k-fair, fair total, and connected k-fair domination numbers, respectively, of these graphs. This study combines the concepts of neighborhood connected domination in graphs and of k-fair domination in graphs. A neighborhood connected k-fair dominating set (nckfd-set) is a k-fair dominating set S ⊆ V (G) such that the induced subgraph 〈N(S)〉 is connected. The neighborhood connected k-fair domination number of G, denoted by γnckfd(G), is the minimum cardinality of an nckfd-set. An nckfd-set in G with cardinal- ity γnckfd(G) is referred to as a γnckfd-set. 2. Preliminary Results Remark 1. Every nckfd-set is an ncd-set, where k is a positive integer. Remark 2. For any connected graph G of order m ≥ 2 and a positive integer k, 1 ≤ γ(G) ≤ γkfd(G) ≤ γnckfd(G) ≤ m and γ(G) ≤ γnc(G) ≤ γnckfd(G). The bounds given above are sharp. However, the inequalities can be attained. To see this, consider G = K4 and H = C6. Clearly, 1 = γ(G) = γ1fd(G) = γnc1fd(G) < m. Moreover, γnc4fd(G) = 4 = m while γ(G) < γ2fd(G) = γnc2fd(G) = 2. Furthermore, it can be easily verified that 1 < 2 = γ(H) = γ1fd(H) < γnc1fd(H) = 4. Proposition 1. Let G be a connected graph of order n ≥ 2 and k a positive integer such that k ≤ n. Then the following hold: (i) γnckfd(G) ≥ k. W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1339 (ii) γnckfd(G) = k if and only if G has an nckfd-set S with |S| = k. (iii) γnckfd(Kn) = k. Proof. (i) let S be a γnckfd-set. If S = V (G), then γnckfd(G) = |S| = n ≥ k. Suppose S 6= V (G) and let v ∈ V (G)\S. Then |NG(v) ∩ S| = k ≤ |S| = γnckfd(G). (ii) Next, suppose that γnckfd(G) = k. Then G has an nckfd-set S with γnckfd(G) = |S| = k. For the converse, suppose that G has an nckfd-set S with |S| = k. Then γnckfd(G) ≤ |S| = k. Since γnckfd(G) ≥ k, it follows that γnckfd(G) = k. Thus, (ii) holds. (iii) Let G be Kn. Clearly, S = V (Kk) is a kfd-set of Kn, 〈N(S)〉 = Kn−1 if k = 1 and 〈N(S)〉 = Kn if k > 1, so S is an nckfd-set of Kn. The result now follows by (ii). � Remark 3. [1] (i) γnc ≥ γ. (ii) For any connected graph G, γnc = 1 if and only if there exists a non-cut vertex v such that deg v = n − 1 . Thus, γnc(G) = 1 if and only if G = H + K1 for some connected graph H. Theorem 1. [1] For any positive integer n ≥ 1, γnc(Pn) = dn2 e. Theorem 2. [1] γnc(Cn) = { dn2 e, if n � 3(mod 4) bn2 c, if n ≡ 3(mod 4). Theorem 3. For any positive integer n ≥ 1, γnc1fd(Pn) = dn2 e. Proof. Let Pn = [v1, v2, ..., vn]. Clearly, the formula holds for n = 1, 2, 3. Let l be a positive integer. If n = 4l, then S = {vi : i = 2a, 2a+ 1, a is odd and 1 ≤ a ≤ 2l− 1} is an nc1fd-set of Pn, where 〈N(S)〉 = Pn. If n = 4l+ 1, then S1 = S ∪ {vn−1} is an nc1fd-set of Pn, where 〈N(S1)〉 = Pn. If n = 4l + 2, then S2 = S ∪ {vn} is an nc1fd-set of Pn, where 〈N(S2)〉 = Pn−1. Finally, if n = 4l + 3, then S3 = S ∪ {vn−1, vn} is an nc1fd-set of Pn, where 〈N(S3)〉 = Pn. Hence, γnc1fd(Pn) ≤ dn2 e. Further, if S is any γnc1fd-set of Pn, then S is an ncd-set of Pn. By Remark 2 and Theorem 1, |S| ≥ dn2 e. Therefore, γnc1fd(Pn) = dn2 e. � Theorem 4. For any positive integer n ≥ 3, γnc1fd(Cn) =  dn2 e, if n ≡ 0 or 1(mod 4) dn2 e+ 1, if n ≡ 2(mod 4) bn2 c, if n ≡ 3(mod 4). W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1340 Proof. Let Cn = [v1, v2, ..., vn, v1]. Clearly, γnc1fd(C3) = 1. Let l be a positive integer and n = 4l+ r, where 0 ≤ r ≤ 3. Let S = {vi : i = 2j, 2j+ 1, j is odd and 1 ≤ j ≤ 2l− 1}. Let S1 =  S, if n ≡ 0(mod 4) S ∪ {v1}, if n ≡ 1(mod 4) S ∪ {v1, vn}, if n ≡ 2(mod 4) S ∪ {vn−1}, if n ≡ 3(mod 4). Clearly, S1 is a 1fd-set of Cn. Moreover, 〈N(S1)〉 = { Cn, if n � 3(mod 4) Pn−1, if n ≡ 3(mod 4), thus, S1 is an nc1fd-set of Cn. Hence, γnc1fd(Cn) ≤  dn2 e, if n ≡ 0 or 1(mod 4) dn2 e+ 1, if n ≡ 2(mod 4) bn2 c, if n ≡ 3(mod 4). Now, let S be any γnc1fd-set of Cn. By Remark 2 and Theorem 2, γnc1fd(Cn) ≥ γnc(Cn) = { dn2 e, if n � 3(mod 4) bn2 c, if n ≡ 3(mod 4). If n ≡ 0 or 1(mod 4), then γnc1fd(G) ≥ dn2 e. If n ≡ 3(mod 4), then γnc1fd(G) ≥ bn2 c. Moreover, when n ≡ 2(mod 4) , then 〈S1〉 contains two vertices more than when n ≡ 0(mod 4) and one vertex more than when n ≡ 1(mod 4). Thus, γnc1fd(Cn) ≥ dn2 e + 1 if n ≡ 2(mod 4). The result now follows. � Theorem 5. For any nontrivial connected graph G, γnc1fd(G) = 1 if and only if G = H +K1 for some connected graph H. Proof. Suppose γnc1fd(G) = 1. Then by Remark 2, γnc(G) = 1, thus G = H + K1 for some connected graph H by Remark 3. Conversely, suppose G = H + K1 for some connected graph H. Let 〈S〉 = K1 = 〈{v}〉. Then 〈N(S)〉 = H and clearly S is a γnc1fd-set of G. Hence, γnc1fd(G) = 1. � Corollary 1. Let n be a positive integer. Then γnc1fd(Fn) = γnc1fd(K1,n) = 1 for n ≥ 1 and γnc1fd(Wn) = 1 for n ≥ 3. Theorem 6. 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 γnc1fd(G) = b. W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1341 ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ........................... ........................... x1 x2 x3 x4 x5 xa−1 xa · · ·• •• ••• • y1 y2 y3 y4 y5 ya−1 ya z1 z2 z3 z4 z5 za−1 za Figure 1: A graph G with γ1fd(G) = γnc1fd(G) = a = b. Proof. Consider the following cases: Case 1. a = b Let G be the graph shown in Figure 1. It is clear that the set A = {xi : i = 1, 2, ...a} is both a γ1fd-set and a γnc1fd-set in G. It follows that γ1fd(G) = γnc1fd(G) = |A| = a = b. Case 2. a < b Subcase 1. b = a+ 1 Let G be the graph shown in Figure 2. Then A = {x1, x2, ..., xa} is a γ1fd-set of G and B1 = A ∪ {q} and B2 = {x1, x2, ..., xa−1, w, q} are the (only) γnc1fd-sets of G. Thus, γ1fd(G) = a and γnc1fd(G) = b = a+ 1. ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ........................... ........................... x1 x2 x3 x4 x5 xa−1 w v xa q · · ·• •• •• • • • y1 y2 y3 y4 y5 ya−1 z1 z2 z3 z4 z5 za−1 Figure 2: A graph G with γ1fd(G) = a and γnc1fd(G) = b when a < b. Subcase 2. b ≥ a+ 2 Let r = b− a ≥ 2. Let H1 and H2 be graphs such that H1 ∼= H2 ∼= Kr. Consider the graph G in Figure 3 . ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ ................................................................................................................ ................................................................................................................ ........................................ .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... . ......................................... ........................................ ........................................ .......................... ......................................................................................................................................................................................... ................................................................................................................................................... ........................................................................................................................... ........................................................................................................................... ............ ........... ........... .......... ......... ......... ......... ........ ........ ........ ......... ......... .......... .......... ......... ......... ........ ........ ........ ........ ......... ......... .......... .......... ........... ............ .. ........................................................................................................................................................................................ .................. ................. ................. .............................. .................. .................. .............................. ................ ................ ......... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ........................... ........................... ................... .................. .................. .................. ............. .......................................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ................................................................................................................................................... .................................... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ...... ............................................................................................................................................................................................................. .................................... .................................... x1 x2 x3 x4 x5 xa−1 w v xa p1 p2 pr · · ·• •• •• • • H1 H2··· y1 y2 y3 y4 y5 ya−1 z1 z2 z3 z4 z5 za−1 Figure 3: A graph G with γ1fd(G) = a and γnc1fd(G) = b when a < b and b− a ≥ 2. Clearly, A1 = {x1, x2..., xa} is a γ1fd-set of G. Let B be a γnc1fd-set of G. Then W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1342 clearly, {x1, x2, ..., xa−1} ⊆ B. Suppose xa /∈ B. Then V (Hj) ∩ B 6= ∅ for j = 1, 2, contrary to the assumption that B is a 1fd-set. Therefore, xa ∈ B. If w /∈ B, then v, pi /∈ B for all i ∈ {1, 2, ..., r}. Since B is a γnc1fd-set, B = {x1, x2, ..., xa} ∪ V (H1) or B = {x1, x2, ..., xa} ∪ V (H2), where ∣∣B∣∣ = a + r = b. Suppose that w ∈ B. Since B is a 1fd-set, it follows that v, pi ∈ B for all i ∈ {1, 2, ..., r}. Hence, B = {x1, x2, ..., xa, w, v} ∪ {p1, p2, ..., pr} and ∣∣B∣∣ = b+ 2. This is not possible because {x1, x2, ..., xa} ∪ V (H1) is an nc1fd-set having exactly b elements. Therefore, w /∈ B and B = {x1, x2, ..., xa} ∪ V (H1) or B = {x1, x2, ..., xa} ∪ V (H2). Accordingly, γ1fd(G) = a and γnc1fd(G) = b. � Corollary 2. γnc1fd − γ1fd can be made arbitrarily large. Theorem 7. Let a and b be positive integers such that 4 ≤ a ≤ b. Then there exists a connected graph G such that γ2fd(G) = a and γnc2fd(G) = b. Proof. Consider the following cases: Case 1. a = b Let G be the graph shown in Figure 4. Clearly, the set B = {xi : i = 1, 2, ...a} is both a γ2fd-set and a γnc2fd-set in G. It follows that γ2fd(G) = γnc2fd(G) = |B| = a = b. ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... ............................................................... ........................... x1 x2 x3 x4 x5 xa−1 xa · · ·• •• ••• • y1 y2 y3 y4 y5 ya−1 z1 z2 z3 z4 z5 za−1 Figure 4: A graph G with γ2fd(G) = γnc2fd(G) = a = b. Case 2. a < b Let m = b− a and let H1, H2, H3 and H4 be graphs such that H1 ∼= H2 ∼= H3 ∼= H4 ∼= Km. Consider the graph G in Figure 5. Clearly, A1 = {x1, x2, ..., xa} is a γ2fd-set of G. Suppose A is a γnc2fd-set of G. It is easy to show that {x1, x2, ..., xa−2} ⊆ A. Suppose that xa−1 /∈ A. Then ya−2, za−2 ∈ A. This implies that ya−1 /∈ A and V (H1) ∩ A = ∅. Hence, ∣∣NG(ya−1) ∩ A ∣∣ ≤ 1, a contradiction. Thus, xa−1 ∈ A. Suppose that xa /∈ A. Then ∣∣V (H3) ∩ A ∣∣ = 1 and∣∣V (H4) ∩ A ∣∣ = 1. It follows that V (H1) ∩ A = ∅ and ya−1 /∈ A. This, however, implies that NG(ya−1) ∩ A = {xa−1}, a contradiction. Therefore, A1 ⊆ A. Since 〈NG(A1)〉 is not connected, |A1| = a < |A|, that is, A1 6= A. Let v ∈ A\A1. If v = ya−1 or v ∈ V (H1), then {ya−1} ∪ V (H1) ⊆ A. If v = za−1 or v ∈ V (H2), then {za−1} ∪ V (H2) ⊆ A. Let B = A1 ∪ {ya−1} ∪ V (H1) or B = A1 ∪ {za−1} ∪ V (H2). Then B is an nc2fd-set of G. Hence, |A| ≤ |B| = b + 1. Now, if v ∈ V (H3), then V (H3) ⊆ A. Similarly, if v ∈ V (H4), then V (H4) ⊆ A. Let A∗ = A1 ∪ V (H3) or A∗ = A1 ∪ V (H4). Then A∗ is an nc2fd-set of G and |A∗| = b < |B|. Since such v exists, A = A1∪V (H3) or A = A1∪V (H4). Therefore, γ2fd(G) = |A1| = a and γnc2fd(G) = |A| = b. � W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1343 ................................................................................................................ ................................................................................................................ .................................... ....................................................................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ...................................................................................................................................................................................... .................................... .................................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. . .................................... .................................... ...................................................................................................................................................................................... .................................... .................................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. . .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... . .......................... ......................... ......................... ......................... ......................... ......................... ......................... ....... ................. ................ ................ ........... ................... .................. .................. .... ................. ................ ................ .. ........................................................................................................................ ........................................................................................................................ .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ............. ................................................ ................................................ ................................................ ................................................ ................................................ ................................................ ................................................ .. .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ................................................................................................................................................................................... ........... .......... .......... .......... .......... .. .......... ......... ......... ......... ......... ......... ..... .......... ......... ......... ......... ......... ......... ............ ............... ........................ ..................................................................... ........................................................................................... ............... ............. . ................... .................. ................. ................. ................ ................ ............... ............... ............... .............. .............. .............. ............. ............. ............. ............. ............. ............. ............ ............ ......... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .... ............................................................................................... ............................. ....................... .................... .................. ................. ................ ............... .............. .............. ....... ................ ................ ................ ................ ................ ................ ................ ................ ................ ............ ........................................................................................................................................................................................................... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ...... ................................................... .............................................................. ........................................................ ........................................................................................... ............... ............. . ............ ............... ........................ ..................................................................... ............................................................................................................................................................................................................................................................................................................. ..................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................ ............................................................................................................................................................ .................................................................................................................................................................................................................................................... ....................................................................................................................................................................................... ............................................................ ........................................................... ................................................... ........... .......... ......... ......... ......... ........ ........ ........ ......... ......... ......... .......... ........... ........... .......... ......... ......... ......... ........ ........ ........ ......... ......... ......... .......... ........... ..................................................................................................................................................................................................................................................................................................................................................................................... .................................................................................................................................................................................................................................................................................................................................................. H4 H3 H1 H2 · · · x1 x2 x3 xa−3 xa−2 xa−1 xa ya−3 ya−2 ya−1 za−3 za−2 za−1 • •• ••• • y1 y2 y3 z1 z2 z3 Figure 5: A graph G with γ2fd(G) = a and γnc2fd(G) = b when a < b. Corollary 3. γnc2fd − γ2fd can be made arbitrarily large. Theorem 8. [6] Let G and H be nontrivial connected graphs of orders m and n, respec- tively, and k a positive integer with 1 ≤ k ≤ max{m,n}. Then S ⊆ V (G+H) is a kfd-set of 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 of 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 = ∅ (k = 1) or B = ⋃ v∈V (G) Sv, where each Sv is a (k − 1)fd-set of Hv (k ≥ 2). (b) C = ⋃ v∈V (G) Sv, where each Sv is a kfd-set of 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: W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1344 (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 4. [6] Let G and H be nontrivial connected graphs of orders m and n, respec- tively, and k a positive integer with 1 ≤ k ≤ min{m,n}. If D is a kfd-set in H, then V (G)×D is a kfd-set in G�H. 3. Neighborhood Connected k-Fair Domination in the Join of Graphs 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)}. Theorem 11. 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 an nckfd-set in G+H if and only if S is a kfd-set in G+H. Proof. Let S ⊆ V (G+H) be an nckfd-set in G+H. Then by definition, S is a kfd-set in G+H. For the converse, suppose S ⊆ V (G+H) is a kfd-set in G+H. Then at least one of Statements (a) to (f) of Theorem 8 holds. We claim that 〈N(S)〉 is connected. If State- ment (a) holds, that is, S = V (G + H), then we are done. Suppose Statement (b) holds; that is, S ⊆ V (G), |S| = k and S is a kfd-set of G. Then 〈NG+H(S)〉 = 〈NG(S)〉 + H, which is connected. Similarly, if Statement (c) holds, then 〈NG+H(S)〉 = G+ 〈NH(S)〉 is connected. Suppose Statement (d) holds; that is, S = SG∪SH , where SG is a (k−|SH |)fd- set in G and SH is a (k− |SG|)fd-set in H. Then NG+H(S) = NG+H(SG)∪NG+H(SH) = [NG(SG) ∪ V (H)]∪ [NH(SH) ∪ V (G)] = V (G + H). Hence, 〈NG+H(S)〉 = G + H is con- nected. Suppose Statement (e) holds; that is, S = V (G) ∪ T , where |V (G)| = m < k and T is a (k−m)fd-set in H. Then NG+H(S) = NG+H(V (G))∪NG+H(T ) = V (H)∪ [V (G)∪ NH(T )] = V (G)∪V (H). Thus, 〈NG+H(S)〉 = G+H is connected. Similarly, if Statement (f) holds, that is, S = D ∪ V (H), where |V (H)| = n < k and D is a (k − n)fd-set in G, then 〈NG+H(S)〉 = G+H is connected. Therefore, S is an nckfd-set in G+H. � The next result immediately follows from Theorem 11. Corollary 5. 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, γnckfd(G + H) = γkfd(G + H). In particular, if G or H has a kfd-set S with |S| = k, then γnckfd(G+H) = k. W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1345 4. Neighborhood Connected k-Fair Domination in the Corona of Graphs 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. Theorem 12. Let G and H be nontrivial connected graphs, and let k be a positive integer with 2 ≤ k ≤ |V (H)|. Then C ⊆ V (G ◦H) is an nckfd-set in G ◦H if and only if C is a kfd-set in G ◦H. Proof. If C is an nckfd-set in G ◦H, then C is a kfd-set in G ◦H. Conversely, let C be a kfd-set in G ◦H. Then by Theorem 9, (a) C = V (G) ∪ B, where B = ∅ when k = 1 and B = ⋃ v∈V (G) Sv, where each Sv is a (k − 1)fd-set of Hv when k ≥ 2, or (b) C = ⋃ v∈V (G) Sv, where each Sv is a kfd-set of Hv and |Sv| = k. We claim that 〈N(C)〉 is connected. Suppose Condition (a) holds. Suppose further that B = ∅. Then C is a 1fd-set and 〈N(C)〉 = G◦H, which is connected. We next assume that B = ⋃ v∈V (G) Sv, where each Sv is a (k−1)fd-set in Hv. Then 〈N(C)〉 = 〈 ⋃ v∈V (G) (v+Hv) 〉 = G◦H is connected. Suppose Condition (b) holds. Then 〈N(C)〉 = 〈 ⋃ v∈V (G) ({v}∪NHv(Sv)) 〉 which is connected. Therefore, C is an nckfd-set in G ◦H. � Corollary 6. Let G and H be nontrivial connected graphs of orders m and n, respectively, and let k be a positive integer with 1 ≤ k ≤ n. Then γnc1fd(G ◦H) = m. For k ≥ 2, γnckfd(G ◦H) = { mk, if H has a kfd-set with |S|=k m(1 + γ(k−1)fd(H), if H has no kfd-set with |S|=k. Proof. This immediately follows from Theorem 12 (and its proof) . � 5. Neighborhood Connected k-Fair Domination in the Lexicographic Product of Graphs 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). W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1346 Theorem 13. 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 C = ⋃ x∈S ( {x}×Tx ) ⊆ V (G[H]) is an nckfd-set in G[H] if and only if the following conditions hold: (i) S is a dominating set in G. (ii) For each x ∈ S∩NG(S) with Tx 6= V (H), Tx is an rfd-set and ∑ z∈NG(x)∩S |Tz| = k−r for some r < k. (iii) For each x ∈ S\NG(S) with Tx 6= V (H), |Tx| = k and Tx is a kfd-set in H. (iv) For each y ∈ V (G)\S, ∑ v∈NG(y)∩S |Tv| = k. Proof. Suppose C = ⋃ x∈S ( {x}×Tx ) is an nckfd-set in G[H]. Then C is a kfd-set in G[H], hence Statements (i) to (iv) hold by Theorem 10. For the converse, suppose Statements (i) to (iv) hold. We claim that 〈NG[H](C)〉 is connected. Suppose C 6= V (G[H]). Let (x, a), (y, b) ∈ NG[H](C) such that (x, a) 6= (y, b) and (x, a)(y, b) /∈ E(〈NG[H](C)〉). Consider the following cases: Case 1. x = y Let z ∈ V (G) ∩ NG(x). If z ∈ S, pick any c ∈ Tz and let d ∈ NH(c). Then (z, d) ∈ NG[H](z, c) ⊆ NG[H](C) and [(x, a), (z, d), (y, b)] is an (x, a)-(y, b) geodesic in NG[H](C). If z /∈ S, then {z} × Tz ⊆ NG[H](C) since S is a dominating set of G. Thus, [(x, a), (z, d), (y, b)] is an (x, a)-(y, b) geodesic in NG[H](C) for all d ∈ Tz. Case 2. x 6= y Let [x1, x2, ..., xk], where x1 = x and xk = y, be an x-y geodesic. Since S is a domi- nating set of G, ( {xj}× Txj ) ∩NG[H](C) 6= ∅ for each j ∈ {2, 3, ..., k− 1}. Pick (xj , aj) ∈ NG[H](C) for each j ∈ {2, 3, ..., k − 1}. Then [(x1, a1), (x2, a2), ..., (xk−1, ak−1), (xk, ak)], where a1 = a and ak = b, is an (x, a)-(y, b) path in NG[H](C). Therefore, 〈NG[H](C)〉 is connected. Hence, C is an nckfd-set in G[H]. � The next result immediately follows from Theorem 13 and Theorem 10. Corollary 7. 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 C = ⋃ x∈S ( {x} × Tx ) ⊆ V (G[H]) is an nckfd-set in G[H] if and only if C is a kfd-set in G[H]. In particular, γnckfd(G[H]) = γkfd(G[H]). 6. Neighborhood Connected k-Fair Domination in the Cartesian Product of Graphs The Cartesian 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 condi- tions: (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). W. Bent-Usman, R. Isla, S. Canoy / Eur. J. Pure Appl. Math, 12 (3) (2019), 1337-1349 1347 Theorem 14. Let G and H be nontrivial connected graphs. If S1 and S2 are kfd-sets in G and H, respectively, then C1 = S1 × V (H) and C2 = V (G) × S2 are nckfd-sets in G�H. Proof. Let S1 be a kfd-set in G. By Corollary 4, C1 = S1 × V (H) is a kfd-set of G�H. Next, let (x, a) and (y, b) be distinct non-adjacent vertices of 〈NG(C1)〉. Consider the following cases: Case 1. x = y Let [a1, a2, ..., ak], where a1 = a and ak = b, be an a-b geodesic. If x ∈ S1, then {x} × V (H) ⊆ NG�H(C1). It follows that [(x, a1), (x, a2)..., (x, ak)] is an (x, a)-(y, b) path in 〈NG�H(C1)〉. If x /∈ S1, then there exists z ∈ S1 ∩NG(x) since S1 is a dominating set of G. Since {z}×V (H) ⊆ C1, {x}×V (H) ⊆ NG�H(C1). Hence, [(x, a1), (x, a2)..., (x, ak)] is an (x, a)-(y, b) path in 〈NG�H(C1)〉. Case 2. x 6= y Let [x1, x2, ..., xk], where x1 = x and xk = y, be an x-y geodesic. Let j ∈ {1, 2, ..., k}. If xj ∈ S1, then {xj} × V (H) ⊆ C1; hence, {xj} × V (H) ⊆ NG�H(C1) (since H is connected). If xj ∈ S1, then there exists zj ∈ S1 ∩ NG(xj) because S1 is a dominat- ing set. Since {zj} × V (H) ⊆ C1, it follows that {xj} × V (H) ⊆ NG�H(C1). Hence, if a = b, then [(x1, a), (x2, a)..., (xk, a)] is an (x, a)-(y, b) path in 〈NG�H(C1)〉. Sup- pose a 6= b. Let [a1, a2, ..., ar], where a1 = a and ar = b, be an a-b geodesic. Then [(x1, a1), (x2, a1)..., (xk, a1), (xk, a2), ..., (xk, ar)] is an (x, a)-(y, b) path in 〈NG�H(C1)〉. Therefore, C1 is an nckfd-set in G�H. Similarly, if S2 is a kfd-set in H, then C2 = V (G)× S2 is an nckfd-set in G�H. � Corollary 8. Let G and H be nontrivial connected graphs and ∅ 6= S1 ⊆ V (G). The following are equivalent: (i) S1 is a kfd-set of G. (ii) C1 = S1 × V (H) is a kfd-set of G�H. (iii) C1 = S1 × V (H) is an nckfd-set of G�H. Proof. By Corollary 4, (i) implies (ii). Suppose C1 is a kfd-set of G�H. Let v ∈ V (G)\S1 and let a ∈ V (H). Then (v, a) /∈ C1 and |NG�H((v, a))∩C1| = |NG(v)∩S1| = k since C1 is a kfd-set. Thus, S1 is a kfd-set of G and (ii) implies (i). By Theorem 14, (i) implies (iii). By definitions of kfd-set and nckfd-set, (iii) implies (ii). Therefore, Statements (i), (ii), and (iii) are equivalent. � Corollary 9. 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 γnckfd(G�H) ≤ min{n · γkfd(G),m · γkfd(H)}. In particular, γnckfd(G�Kn) ≤ min{n · γkfd(G),mk} . REFERENCES 1348 Remark 4. The bound given in Corollary 9 is sharp. However, the strict inequality can be attained. To see this, consider the graphs shown in Figure 6. The shaded vertices in each graph form a γnckfd-set. Thus, (a) γnc1fd(K3�P2) = 2 = min{2 · 1, 3 · 1} = min{|V (P2)| ·γ1fd(K3), |V (K3)| ·γ1fd(P2)}, (b) γnc2fd(P3�C4) = 6 = min{4 · 2, 3 · 2} = min{|V (C4)| · γ2fd(P3), |V (P3)| · γ2fd(C4)}, and (c) γnc2fd(P3�P4) = 7 < min{4 · 2, 3 · 3} = min{|V (P4)| · γ2fd(P3), |V (P3)| · γ2fd(P4)}. ................................................................................... .................................... ................................................................................... .................................... ................................................................................... .................................... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ......... ......... ........ ........ ........ ........ ........ ........ ........ ......... ......... ....... ......... ......... ......... ........ ........ ........ ........ ........ ........ ........ ......... ......... ....... • • (a) ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... .................................... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ................ ................... ............................. ............................................................................................................. ................ ................... ............................. ............................................................................................................. ................ ................... ............................. .............................................................................................................• • • • • • (b) ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... .................................... ................................................................................... ................................................................................... ................................................................................... .................................... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ......• • • • • • • (c) Figure 6: The graphs K3�P2, P3�C4 and P3�P4. Acknowledgements This research is funded by the the Philippine Commission on Higher Education-Faculty Development Program Phase II (CHED-FDP II) and the Mindanao State University-Iligan Institute of Technology. References [1] S. Arumugam and C. Sivagnanam. Neighborhood Connected Domination in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 73:55–64, 2010. [2] W. M. Bent-Usman D. P. Gomisong and R. T. Isla. Connected k-Fair domination in the Join, Corona, Lexicographic and Cartesian Products of Graphs. Applied Mathematical Sciences, 12:1341–1355, 2018. [3] Y. Caro A. Hansberg and M. A. Henning. Fair domination in graphs. Discrete Math- ematics, 19:1–18, 2011. [4] E. Maravilla R. Isla and S. R. Canoy Jr. Fair Domination in the Join, Corona and Composition of Graphs. Applied Mathematical Sciences, 93:4609–4620, 2014. REFERENCES 1349 [5] E. Maravilla R. Isla and S. R. Canoy Jr. Fair Total Domination in the Join, Corona and Composition of Graphs. International Journal of Mathematical Analysis, 54:2677– 2685, 2014. [6] E. Maravilla R. Isla and S. R. Canoy Jr. k-fair Domination in the Join, Corona, Com- position and Cartesian product of Graphs. Applied Mathematical Sciences, 178:8863– 8874, 2014.