EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 4, 2022, 1966-1981 ISSN 1307-5543 – ejpam.com Published by New York Business Global Outer-connected Hop Dominating Sets in Graphs Chrisley Jade C. Saromines1,∗, Sergio R. Canoy, Jr.1 1 Department of Mathematics and Statistics, College of Science and Mathematics, Center for Graph Theory, Algebra and Analysis-PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. Let G be an undirected graph with vertex and edge sets V (G) and E(G), respectively. A hop dominating set S ⊆ V (G) is called an outer-connected hop dominating set if S = V (G) or the subgraph ⟨V (G) \ S⟩ induced by V (G) \ S is connected. The minimum size of an outer-connected hop dominating set is the outer-connected hop domination number γ̃ch(G). A dominating set of size γ̃ch(G) of G is called a γ̃ch-set. In this paper, we investigate the concept and study it for graphs resulting from some binary operations. Specifically, we characterize the outer-connected hop dominating sets in the join, corona and lexicographic products of graphs, and determine bounds of the outer-connected hop domination number of each of these graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Hop domination, outer-connected, join, corona, lexicographic 1. Introduction As pointed out in [1] and [9], the domination concept has been one of the mainstreams of research in Graph Theory and it has numerous applications, interesting questions and results, and unsolved research questions. Moreover, the concept has already plenty of variations (see [3], [8], [13], [15], [17], [18]). Outer-connected domination, a variation of domination, was first introduced by Cyman in 2007 [5]. A set D ⊆ V (G) is said to be an outer-connected dominating set of G if D is dominating and either D = V (G) or ⟨V (G) \D⟩ is connected. This concept has been studied by several authors like Jiang and Shang [11] and Ahkbari et al. [2], and an outer- connected domination variant was introduced in [12]. In 2015, Natarajan and S. K. Ayyaswamy [16] introduced a new distance related dom- ination parameter and called it the hop domination number of a graph. As defined in [16], a subset S of V (G) is a hop dominating set of G if for every v ∈ V (G) \ S, there exists ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i4.4590 Email addresses: chrisleyjade.saromines@g.msuiit.edu.ph (C.J. Saromines), sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) https://www.ejpam.com 1966 © 2022 EJPAM All rights reserved. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1967 u ∈ S such that dG(u, v) = 2.The concept and some of its variants are also studied in [4], [10], [14], [19], and [20]. Motivated by the hop domination concept and the introduction of the outer-connected domination concept by Cyman, the authors will try to introduce and make an initial study of the concept of outer-connected hop domination. Since domination and hop domina- tion (including their respective variations) have similar applications (e.g. in modeling facility location and protection strategy problems), these two variants can have similar applications as well. 2. Terminology and Notation For any two vertices u and v in an undirected connected graph G, the distance dG(u, v) is the length of a shortest path joining u and v. Any u-v path of length dG(u, v) is called a u-v geodesic. The open neighborhood of a point u is the set NG(u) consisting of all points v which are adjacent to u. The closed interval I [x, y] consists of x, y and all vertices lying on some x-y geodesic of G and, for S ⊆ V (G), I [S] = ⋃ x,y∈S I [x, y]. The closed neighborhood of u is NG[u] = NG(u) ∪ {u}. For any A ⊆ V (G), NG(A) = ⋃ v∈A NG(v) is called the open neighborhood of A andNG[A] = NG(A)∪A is called the closed neighborhood of A. The open hop neighborhood of a point u is the set N2 G(u) = {v ∈ V (G) : dG(v, u) = 2}. The closed hop neighborhood of u is N2 G[u] = N2 G(u) ∪ {u}. For any A ⊆ V (G), N2 G(A) = ⋃ v∈A N2 G(v) is called the open hop neighborhood of A and N2 G[A] = N2 G(A)∪A is called the closed hop neighborhood of A. A set S ⊆ V (G) is a dominating set of G if for every v ∈ V (G) \ S, there exists u ∈ S such that uv ∈ E(G), that is, NG [S] = V (G). The minimum cardinality of a dominating set of a graph G, denoted by γ(G), is called the domination number of G. A set S ⊆ V (G) is an outer-connected dominating set of G if S is dominating and either S = V (G) or the subgraph ⟨V (G) \ S⟩ induced by V (G) \ S is connected. The minimum cardinality of an outer-connected dominating set of a graph G, denoted by γ̃c(G), is called the outer- connected domination number of G. A dominating set (resp. outer-connected dominating set) S of G with |S| = γ(G) (resp. |S| = γ̃c(G)) is referred to as a γ-set (resp. γ̃c-set) of G. A set S ⊆ V (G) is a hop dominating set (resp. total hop dominating set) if N2 G[S] = V (G) (resp. N2 G(S) = V (G)). The minimum cardinality of a hop dominating set (resp. total hop dominating set) of a graph G, denoted by γh(G) (resp. γth(G)) is called the hop domination number (resp. total hop domination number) of G. A hop dominating set (resp. total hop dominating set) of G with cardinality equal to γh(G) (resp. γth(G)) is referred to as a γh-set (resp. γth-set) of G. A hop dominating set S ⊆ V (G) is called an outer-connected hop dominating set if S = V (G) or ⟨V (G) \ S⟩ is connected. The minimum cardinality of an outer-connected hop dominating set of a graph G, denoted by γ̃ch(G), is called the outer-connected hop domination number of G. An outer-connected hop dominating set of size γ̃ch(G) of G is C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1968 called a γ̃ch-set. A set D ⊆ V (G) is pointwise non-dominating if for each v ∈ V (G) \ D, there exists u ∈ D such that v /∈ NG(u). The minimum cardinality of a pointwise non-dominating set of a graph G, denoted by pnd(G), is called the pointwise non-domination number of G. A pointwise non-dominating set D of V (G) is an outer-connected pointwise non-dominating set if D = V (G) or ⟨V (G) \D⟩ is connected. The minimum cardinality of an outer- connected pointwise non-dominating set of a graph G, denoted by p̃nd(G), is called the outer-connected pointwise non-domination number of G. Let G and H be any two graphs. The join G + H is the graph with vertex set V (G+H) = V (G)∪ V (H) and edge set E(G+H) = E(G)∪E(H)∪ {uv : u ∈ V (G), v ∈ V (H)}. The corona G ◦ H is the graph obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H. We denote by Hv the copy of H in G ◦ H corresponding to the vertex v ∈ G and write v + Hv for ⟨{v}⟩ + Hv. The lexicographic product G[H] is the graph with vertex set V (G[H]) = V (G) × V (H) and (v, a)(u, b) ∈ E(G[H]) if and only if either uv ∈ E(G) or u = v and ab ∈ E(H). Any non-empty set C ⊆ V (G) × V (H) can be written as C = ⋃ x∈S [{x} × Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S. Specifically, Tx = {a ∈ V (H) : (x, a) ∈ C} for each x ∈ S. Some parameters studied on these types of graphs can be found in [6] and [7]. 3. Known Results Proposition 1. [13] Let G be a graph. Then 1 ≤ pnd(G) ≤ |V (G)|. Moreover, (i) pnd(G) = |V (G)| if and only if G is a complete graph, (ii) pnd(G) = 1 if and only if G has an isolated vetex, and (iii) pnd(G) = 2 if and only of G has no isolated vertex and there exist distinct vertices a and b such that NG(a) ∩NG(b) = ∅. Theorem 1. [14] Let G and H be any two graphs. A set S ⊆ V (G+H) is hop dominating set of G+H if and only if S = SG ∪SH , where SG and SH are pointwise non-dominating sets of G and H, respectively. Theorem 2. [14] Let G and H be connected non-trivial graphs. A subset C = ⋃ x∈S [x× Tx] of V (G[H]) is a hop dominating set of G[H] if and only if the following conditions hold: (i) S is a hop dominating set of G; (ii) Tx is a pointwise non-dominating set of H for each x ∈ S with |N2 G(x) ∩ S| = 0. Theorem 3. [14] Let G be a connected graph with γ(G) ̸= 1. If S is a hop dominating set of G, then γth(G) ≤ |S ∩N2 G(S)|+ 2|S \N2 G(S)|. Moreover, γth(G) ≤ 2γh(G). C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1969 4. Results Theorem 4. Let G be any graph on n ≥ 2 vertices. Then 2 ≤ γh(G) ≤ γ̃ch(G) ≤ n. Moreover, (i) γ̃ch(G) = 2 if and only if there exist distinct vertices x, y ∈ V (G) such that ⟨V (G) \ {x, y}⟩ is connected and the following hold: (a) |NG(v) \ {x, y} ∩ {x, y}| ≤ 1 for all v ∈ V (G) \ {x, y}. (b) NG(v)∩NG ({x, y}) ̸= ∅ for all v ∈ V (G)\{x, y} such that NG(v)∩{x, y} = ∅. (c) For all v ∈ V (G)\{x, y}, NG(v)∩NG(x) ̸= ∅ if v ∈ NG(y) and NG(v)∩NG(y) ̸= ∅ if v ∈ NG(x). (ii) γ̃ch(G) = n if and only if every component of G is complete. Proof. Since every outer-connected hop dominating set of G is a hop dominating set, γh(G) ≤ γ̃ch(G). Also, since V (G) is an outer-connected hop dominating set of G and any connected graph G with at least two vertices satisfies 2 ≤ γh(G), it follows that 2 ≤ γh(G) ≤ γ̃ch(G) ≤ n. For (i), suppose that γ̃ch(G) = 2. Let S = {x, y} be a γ̃ch-set of G. Since S is an outer- connected hop dominating set, ⟨V (G) \ {x, y}⟩ is connected. Let v ∈ V (G)\{x, y}. Since S is a hop dominating set, dG(x, v) = 2 or dG(y, v) = 2. Hence, |NG(v) ∩ {x, y}| ≤ 1, showing that (a) holds. If dG(x, v) = 2 (or dG(y, v) = 2), then there exists z ∈ NG(x) ∩ NG(v) (resp. there exists w ∈ NG(y)∩NG(v)). Hence, NG(v)∩NG({x, y}) ̸= ∅ whenever NG(v)∩ {x, y} = ∅, showing (b) holds. Finally, suppose that |NG(v) ∩ {x, y}| = 1. If v ∈ NG(y), then dG(x, v) = 2. Hence, there exist p ∈ NG(v) ∩ NG(x), that is, NG(v) ∩ NG(x) ̸= ∅. Similarly, NG(v) ∩NG(y) ̸= ∅ if v ∈ NG(x). This shows that (c) holds. Conversely, suppose there exist distinct vertices x, y ∈ V (G) such that ⟨V (G) \ {x, y}⟩ is connected and satisfy (a), (b) and (c). Let v ∈ ⟨V (G) \ {x, y}⟩. By (a), |NG(v) ∩ {x, y}| ≤ 1. If |NG(v) ∩ {x, y}| = 0, then dG(v, x) = 2 or dG(v, y) = 2 by (b). Suppose |NG(v) ∩ {x, y}| = 1, say v ∈ NG(y). By (c), NG(v) ∩NG(x) ̸= ∅. This implies that dG(v, x) = 2. Therefore S is an outer-connected hop dominating set of G. Since G is non-trivial, γ̃ch(G) = 2. For (ii), suppose that γ̃ch(G) = |V (G)| and suppose that one component of G, say G1, is not complete. Then there exist distinct vertices x1, y1 ∈ V (G1) such that dG(x1, y1) = 2. Consequently, S = V (G) \ {y1} is an outer-connected hop dominating set of G, contrary to our assumption that γ̃ch(G) = |V (G)|. Thus, every component of G is complete. Suppose every component of G is complete. Suppose γ̃ch(G) = r < |V (G)|, say S is a γ̃ch-set of G. Suppose {G1, G2, ..., Gk} contains all the components of G. Since ⟨V (G) \ S⟩ is connected, there exists m ∈ {1, 2, ..., k} such that V (G) \ S ⊆ V (Gm). Hence, S = (V (Gm) ∩ S) ∪ [∪j ̸=mV (Gj)]. Let v ∈ V (Gm) \ S (this v exists because r < |V (G)|). Since Gm is complete, dG(v, s) = 1 for all s ∈ V (Gm) ∩ S, contrary to the assumption that S is a hop dominating set of G. Therefore, γ̃ch(G) = |V (G)|. Corollary 1. Let G be a graph with n vertices. Then γ̃ch(Kn) = γ̃ch(Kn) = n. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1970 Proposition 2. Let n be a positive integer. (i) For path Pn on n vertices, γ̃ch(Pn) =  2, if n = 3 n− 2, if n = 4, 5, 6 n− 3, if n = 7 n− 4, if n ≥ 8. (ii) For cycle Cn on n vertices, γ̃ch(Cn) =  3, if n = 3 2, if n = 4, 5 n− 4, if n ≥ 6. Proof. (i) Let Pn = [v1, v2, ..., vn]. Clearly, γ̃ch(Pn) = 2 for n = 3, 4. Let n ≥ 5 and let S be a γ̃ch-set of Pn. Since ⟨V (Pn) \ S⟩ is connected and S is a hop dominating set, 2 ≤ |V (Pn) \ S| ≤ 4. Clearly, at least one of v1 and vn is in S. Suppose that v1 ∈ S. Suppose further that |V (Pn) \ S| = 2. Then n = 5 or n = 6. Hence, γ̃ch(P5) = 5 − 2 = 3 and γ̃ch(P6) = 6 − 2 = 4. Next, suppose that |V (Pn) \ S| = 3. If p is the smallest positive integer such that vp /∈ S, then p /∈ {1, 2, n− 3, n− 2}. It follows that v1, v2, vn−1, vn ∈ S. In this case, it can easily be verified that n = 7, and so γ̃ch(P7) = 7− 3 = 4. For n ≥ 8, the set S ′ = V (Pn) \ {v3, v4, v5, v6} is clearly an outer-connected hop dominating set. Thus, γ̃ch(Pn) = n− 4 for all .n ≥ 8. (ii) Let Cn = [v1, v2, ..., vn, v1]. Clearly, γ̃ch(C3) = γ̃ch(K3) = 3. Let n ≥ 4 and let S be a γ̃ch-set of Cn. Since ⟨V (Cn) \ S⟩ is connected and S is a hop dominating set, 2 ≤ |V (Cn) \ S| ≤ 4. If |V (Cn) \ S| = 2, then n = 4. Thus, γ̃ch(C4) = 2. If |V (Cn) \ S| = 3, then n = 5. Hence, γ̃ch(C5) = 2. Suppose n ≥ 6. Then V (Cn) \ {v2, v3, v4, v5} is an outer-connected hop dominating set of Cn. Therefore, γ̃ch(Cn) = n− 4. Theorem 5. Let a and b be positive integers such that 2 ≤ a ≤ b ≤ n. Then there exists a connected graph G such that γh(G) = a and γ̃ch(G) = b. Proof. Suppose that a = b. Consider the graph G = Ka. Then γh(G) = γ̃ch(G) = a. Next, suppose that a < b. Consider the following cases: Case 1. a = 2. Let m = b − a and consider the graph G in Figure 1. Let S1 = {y1, y2} and S2 = {x1, x2, z1, ..., zm}. Then S1 and S2 are γh-set and γ̃ch-set, respectively, of G. Hence, γh(G) = a and γ̃ch(G) = a+m = b. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1971 .................................... .................................... .................................... .................................... .................................... .................................... ............................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... .................................... .................................... .................................... z1 z2 zm y1 y2 x1 x2 ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ..................... .................... .................... .................... .................. ......................................................................................................... ... Figure 1 G : Case 2. a ≥ 3. Let r = b− a+ 1 and consider the graph G ′ in Figure 2. Let D1 = {x1, x2, ..., xa} and D2 = {x1, x2, ..., xa−1, z1, ..., zr}. Then D1 and D2 are γh-set and γ̃ch-set, respectively, of G′. Hence, γh(G ′ ) = a and γ̃ch(G ′ ) = r + a− 1 = b. .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... x1 x2 xa−1 xa ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .. .................................. .................................... ............................................................................ ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................................................................................................................................................. .................................................................................................................................................................. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ............................................................................................................... ............................................................................ .................................................................................................................................................................. ............................................................................ ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .................................... .................................... .................................... .................................... .................................... .................................... z1 z2 zr ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ..................... .................... .................... .................... .................. ......................................................................................................... ............ ........... ........... ........... ........... ........... .... ..................... .................... .................... ....... ........................................................................ ... . . . . . . . . . Figure 2 G ′ : Corollary 2. For each positive integer n, there exists a connected graph G such that γ̃ch(G)− γh(G) = n, that is, γ̃ch- γh can be made arbitrarily large. The next few results deal with the concept of outer-connected pointwise non-dominating sets. Theorem 6. Let G be a graph. Then 1 ≤ pnd(G) ≤ p̃nd(G) ≤ |V (G)|. Moreover, (i) p̃nd(G) = |V (G)| if and only if G is a complete graph, (ii) p̃nd(G) = 1 if and only if G has at most two components such that one of them is the trivial graph, and (iii) p̃nd(G) = 2 if and only if G satisfies one of the following conditions: (a) G has at most two non-trivial components such that one of them is K2. (b) G has exactly three components such that at least two of them are trivial graphs. (c) G is connected non-complete graph and there exist a, b ∈ V (G)(a ̸= b) such that NG(a) ∩NG(b) = ∅ and ⟨V (G) \ {a, b}⟩ is connected. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1972 Proof. Since an empty set cannot be an outer-connected pointwise non-dominating set of G and V (G) is an outer connected pointwise non-dominating set of G, it follows that 1 ≤ p̃nd(G) ≤ |V (G)|. For (i), suppose first that p̃nd(G) = |V (G)| and suppose thatG is not a complete graph. Then there exist non-adjacent vertices x and y of G. Consequently, S = V (G) \ {y} is an outer-connected pointwise non-dominating set of G, contrary to our assumption that p̃nd(G) = |V (G)|.Thus, G must be a complete graph. Conversely, suppose G is a complete graph. Suppose that p̃nd(G) = k < |V (G)|, say S is an p̃nd-set. Choose any w ∈ V (G) \ S. Since S is a pointwise non-dominating set, there exists u ∈ S such that uw /∈ E(G), a contradiction. Therefore, p̃nd(G) = |V (G)|. Next, suppose that p̃nd(G) = 1, say S = {v} is an outer-connected pointwise non- dominating set of G. Since ⟨V (G) \ S⟩ is connected,V (G) \S is contained in a component of G. Thus, G has at most two components and one of them is a trivial graph. Conversely, if G has at most two components G1 and G2 where G1 is a trivial graph, then S = V (G1) is an outer-connected point-wise non-dominating set of G. This shows that (ii) holds. Finally, suppose that p̃nd(G) = 2. Let S1 = {a, b} be an p̃nd-set of G. Case 1. Suppose a, b ∈ V (G1), where G1 is a component of G. If G is connected, then G = G1. If S1 = V (G), then G = K2. Suppose S1 ̸= V (G). Then by (i), G is a non-complete graph. Since S1 is an outer-connected pointwise non-dominating set, NG(a) ∩ NG(b) = ∅ and ⟨V (G) \ S1⟩ is connected. Suppose G is disconnected. Since ⟨V (G) \ S1⟩ is connected, G1 = K2 and G has exactly 2 components G1 and G2. Hence, (a) or (c) holds. Case 2. Suppose a ∈ V (G1) and b ∈ V (G2), where G1 and G2 are distinct compo- nents of G. Suppose G = G1 ∪ G2. Then G1 and G2 are non-trivial graphs by (ii) and the assumption that p̃nd(G) = 2. Hence, ⟨V (G) \ S1⟩ is disconnected, a contradiction. Therefore, G has more than 2 components. This would imply that G1 = G2 = K1. Since ⟨V (G) \ S1⟩ is connected, it follows that G has exactly 3 components. In particular, the G1, G2 and ⟨V (G) \ S1⟩ are the components of G. Thus, (b) holds. Conversely, suppose that (a) holds. If G has only one component, then G = K2. Hence, p̃nd(G) = 2. Suppose G has two non-trivial components, say G1 and G2, where G1 = K2. Let S = V (G1). Clearly, S is a pointwise non-dominating set and ⟨V (G) \ S⟩ = G2 is connected. Hence, p̃nd(G) = 2. Suppose (b) holds. Let G1, G2 and G3 be the components of G such that G1 and G2 are trivial graphs. Let S ′ = V (G1) ∪ V (G2). Clearly, S ′ is a pointwise non-dominating set and 〈 V (G) \ S′ 〉 = G3 is connected. Hence, p̃nd(G) = 2. Suppose (c) holds. Set S ′′ = {a, b} and let w ∈ V (G) \ S′′ . Then by assumption, w is not adjacent to a or b. This implies that S ′′ is a pointwise non-dominating set of G. Since G is connected and non-complete, p̃nd(G) ̸= 1 by (ii). Hence, p̃nd(G) = 2. The next result is a consequence of Theorem 6 (iii)(c). Corollary 3. Let G be a graph on n vertices. Then p̃nd(Pn) = 2 for all n ≥ 3 and p̃nd(Cn) = 2 for all n ≥ 4. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1973 Proposition 3. Let G be a graph with components G1, G2, ..., Gk where k ≥ 2. Then p̃nd(G) = |V (G)| - max {|V (Gj)| : j ∈ {1, ..., k}}. Proof. Let S be a p̃nd-set of G. Since S is outer-connected, ⟨V (G) \ S⟩ is connected. This implies that ⟨V (G) \ S⟩ = Gj for some j ∈ {1, 2, ..., k}. Since S is a p̃nd-set, it follows that |V (Gj)| ≥ |V (Gi| for all i ∈ {1, 2, ..., k} . Therefore, p̃nd(G) = |S| = |∪i ̸=jV (Gi)| = |V (G)| − |V (Gj | = |V (G)| −max {|V (Gi)| : i ∈ {1, 2, ..., k}} . This proves the assertion. Corollary 4. Let G be a disconnected graph of order n ≥ 2. Then p̃nd(G) = n− 1 if and only if G = Kn. Proof. Let G1, G2, ..., Gk be components of G and suppose that p̃nd(G) = n−1. Then, by Proposition 3, max {|V (Gj)| : j ∈ {1, 2, ..., k}} = 1. This implies that Gj = K1 for every j ∈ {1, 2, ..., k}. Therefore, G = Kn. The converse also follows from Proposition 3. Given a complete graph Kn on n ≥ 2 vertices and E ⊆ E(Kn), we denote by Kn \ E the graph obtained from Kn by deleting the edges in set E. Theorem 7. Let G be a connected graph on n ≥ 3 vertices. Then p̃nd(G) = n − 1 if and only if G = Kn \ EG, where EG ⊆ E(Kn) and for some 2 ≤ r ≤ n − 1, ⟨{x : xy ∈ EG for some y ∈ V (G)}⟩ = Kr in G. Proof. Construct a complete graph Kn with V (Kn) = V (G). Then G = Kn\EG where EG ⊆ E(Kn). Let VG = {x : xy ∈ EG for some y ∈ V (G)}. Suppose p̃nd(G) = n− 1, say S = V (G)\{v} is a p̃nd-set of G. Since G is connected and S is pointwise non-dominating, there exists w ∈ V (G) such that dG(v, w) = 2. Hence, vw ∈ EG. Let r be the largest index such that v, w ∈ V (Kr) and V (Kr) ⊆ VG. Since G is connected, 2 ≤ r ≤ n − 1. Let z ∈ NG(v) ∩ NG(w). Suppose that there exists u ∈ V (G) such that uz /∈ E(G). Then V (G) \ {v, z} is an outer-connected pointwise non-dominating set, contrary to our assumption that p̃nd(G) = n− 1. Hence, zy ∈ E(G) for all y ∈ V (G) \ {z}. Suppose now that VG ̸= V (Kr), say q ∈ VG \ V (Kr). By our assumption of r, there exists t ∈ V (Kr) such that qt ∈ E(G). Note that tv, tw /∈ E(G) because t, v, w ∈ V (Kr). Also, since q ∈ VG, there exists x ∈ VG such that xq ∈ EG, that is, xq /∈ E(G). Hence, V (G)\{q, t} is an outer-connected pointwise non-dominating set of G, a contradiction. Thus, ⟨VG⟩ = Kr. For the converse, suppose that G is obtained from Kn as described. Let S be a p̃nd-set of G. Then V (G) \ VG contains all the dominating vertices of G. Consequently, C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1974 V (G) \ VG ⊆ S. Since ⟨V (G) \ S⟩ is connected and ⟨VG⟩ = Kr, S contains all but a single vertex of VG. Thus, p̃nd(G) = |S| = n− 1. Corollary 5. For n ≥ 3, p̃nd(K1,n−1) = p̃nd(Kn \ e) = n− 1, where e ∈ E(Kn). We now characterize the outer-connected hop dominating sets in some graphs under some binary operations. Theorem 8. Let G and H be any two graphs. A set S ⊆ V (G+H) is an outer-connected hop dominating set of G+H if and only if S = SG ∪SH , where SG and SH are pointwise non-dominating subsets of G and H, respectively, such that (i) ⟨V (H) \ SH⟩ is connected whenever SH ̸= V (H) and SG = V (G) and (ii) ⟨V (G) \ SG⟩ is connected whenever SG ̸= V (G) and SH = V (H). Proof. Suppose S is an outer-connected hop dominating set of G+H. Since S is hop dominating, by Theorem 1, S = SG ∪SH where SG and SH are pointwise non-dominating sets of G and H, respectively. Suppose SG = V (G) and SH ̸= V (H). Since S is outer- connected, ⟨V (G+H) \ S⟩ = ⟨V (H) \ SH⟩ is connected. Therefore (i) holds. Similarly, (ii) holds. For the converse, let S = SG ∪ SH , where SG and SH are pointwise non-dominating subsets of G and H, respectively. Then S is a hop dominating set by Theorem 1. If S = V (G+H), then it is an outer-connected hop dominating set. Suppose S ̸= V (G+H). Consider the following cases: Case 1. SG ̸= V (G) and SH ̸= V (H). Then ⟨V (G+H) \ S⟩ = ⟨V (G) \ SG⟩+ ⟨V (H) \ SH⟩ is connected. Case 2. SG = V (G) and SH ̸= V (H). Then ⟨V (G+H) \ S⟩ = ⟨V (H) \ SH⟩ is connected by (i). Case 3. SH = V (H) and SG ̸= V (G). Then ⟨V (G+H) \ S⟩ = ⟨V (G) \ SG⟩ is connected by (ii). Therefore S is an outer-connected hop dominating set of G+H. The next result is based from Proposition 1 (i), Theorem 6, Corollary 3, Corollary 4 and Theorem 8. Corollary 6. Let G and H be any two graphs of orders m and n, respectively. Then γ̃ch(G+H) =  pnd(G) + pnd(H), G and Hare non-complete, |V (G)|+ p̃nd(H), G is complete and His non-complete and |V (H)|+ p̃nd(G), H is complete and Gis non-complete In particular, (i) γ̃ch(G+H) = m+ n, if G and H are complete; C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1975 (ii) γ̃ch(K1,n) = γ̃ch(K1 +Kn) = 1 + p̃nd(Kn) = n for n ≥ 2. (iii) γ̃ch(Fn) = 1 + p̃nd(Pn) = 3 for n ≥ 2. (iv) γ̃ch(Wn) = 1 + p̃nd(Cn) = 3 for n ≥ 4. (v) γ̃ch(Km,n) = pnd(Km) + pnd(Kn) = 2 for m,n ≥ 2. Theorem 9. Let G be a connected graph and let H be any graph. Then a subset C of V (G ◦H) is an outer connected hop dominating set of G ◦H if and only if C = A ∪  ⋃ v∈V (G) Sv  where Sv ⊆ V (Hv) for each v ∈ V (G) and satisfies each of the following statements: (i) A = V (G) or ⟨V (G) \A⟩ is connected. (ii) If A = V (G), then ⟨V (Hv) \ Sv⟩ is a connected proper subgraph of Hv for at most one vertex v ∈ A. Otherwise, Sv = V (Hv) for all v ∈ A. (iii) For all v ∈ (V (G) \N2 G [A]), there exists w ∈ NG(v) such that Sw ̸= ∅. (iv) For all v ∈ (V (G) \NG [A]), Sv is a pointwise non-dominating set of Hv. Proof. Let C be an outer-connected hop dominating set of G ◦H, Sv = V (Hv)∩C for each v ∈ V (G) and set A = V (G)∩C. Suppose A ̸= V (G). If |V (G) \A| = 1, then we are done. Suppose |V (G) \A| ≥ 2. Let u, v ∈ V (G)\A where u ̸= v. Then u, v ∈ V (G◦H)\C. Since ⟨V (G ◦H) \ C⟩ is connected, there is a u-v geodesic P in ⟨V (G ◦H) \ C⟩. Hence, P is a u-v geodesic in ⟨V (G) \A⟩. Thus, ⟨V (G) \A⟩ is connected, showing that (i) holds. Suppose A = V (G). If Sv = V (Hv) for all v ∈ A, then we are done. Suppose there exists v ∈ A such that Sv ̸= V (Hv). Suppose further there exists w ∈ A \ {v} such that Sw ̸= V (Hw). Let p ∈ V (Hv) \ Sv and q ∈ V (Hw) \ Sw. Since every p-q path contains vertices v and w, it follows that there is no p-q path in ⟨V (G ◦H) \ C⟩, contrary to the assumption that ⟨V (G ◦H) \ C⟩ is connected. Hence, there is at most a single vertex v ∈ A such that Sv ̸= V (Hv). Suppose A ̸= V (G). Suppose further that there exists v ∈ A such that Sv ̸= V (Hv). Choose any z ∈ V (G) \ A and y ∈ V (Hv) \ Sv. Since any y-z path contains v as a vertex it follows that there is no y-z path in ⟨V (G ◦H) \ C⟩, a contradiction. Therefore Sv = V (Hv) for all v ∈ A. Hence, (ii) holds. Next, let v ∈ (V (G) \N2 G [A]). Then v /∈ C ∪N2 G(A). Since C is a hop dominating set, there exists y ∈ C ∩N2 G◦H(v). Since v /∈ N2 G(A) and dG◦H(y, v) = 2, it follows that there exists w ∈ NG(v) such that y ∈ Sw. Hence, (iii) holds. Finally, let v ∈ V (G) \ NG [A] and let z ∈ V (Hv) \ Sv. Then z /∈ C. Since C is hop dominating, there exists x ∈ C∩N2 G◦H(z). Hence, x ∈ Sv and dG◦H(z, x) = dHv(z, x) = 2. Therefore, Sv is a pointwise non-dominating set of Hv, showing that (iv) holds. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1976 Conversely, suppose that C has the given form and satisfies properties (i), (ii), (iii) and (iv). Let x ∈ V (G + H) \ C and let v ∈ V (G) such that x ∈ V (v + Hv). Suppose x = v. If v ∈ N2 G(A), then we are done. Suppose v ∈ (V (G)\N2 G [A]. By (iii), there exists w ∈ NG(v) such that Sw ̸= ∅. Choose any p ∈ Sw then p ∈ C and dG◦H = 2. Therefore C is a hop dominating set. Let a, b ∈ V (G ◦H) \ C with a ̸= b and let v, w ∈ V (G) such that a ∈ V (v +Hv) and b ∈ V (w +Hw). Consider the following cases: Case 1. v = w. If a = v and b ∈ V (Hv)\Sv, then ab ∈ E(G◦H) and we are done. Let a, b ∈ V (Hv)\Sv. If A = V (G), then v ∈ A. By (ii), ⟨V (Hv) \ Sv⟩ is connected, hence, there exists an a-b path in ⟨V (Hv) \ Sv⟩. This a-b path is also an a-b path in ⟨V (G ◦H) \ C⟩. If A ̸= V (G), then v /∈ A by the second part of (ii). Therefore, [a, v, b] is an a-b path in ⟨V (G ◦H) \ C⟩. Case 2. v ̸= w. If a = v and b = w, then v, w ∈ V (G) \ A. By (i), there exists an a-b path P in ⟨V (G) \A⟩. Hence, P is a path in ⟨V (G ◦H) \ C⟩. Suppose a ∈ V (Hv) \ Sv and b ∈ V (Hw) \ Sw. By (ii), v, w /∈ A. By (i), there exists a v-w path P = [v1, v2, ..., vk] where v1 = v, vk = w in ⟨V (G) \A⟩. Hence, P ′ = [a, v1, v2, ..., vk, b] is an a-b path in ⟨V (G ◦H) \ C⟩. Suppose a = v and b ∈ (V (Hw) \ Sw). Since v /∈ A, A ̸= V (G). Hence, by the second part of (ii), w /∈ A. It follows from (i) that there exists a v-w path P = [v1, v2, ..., vk] where v1 = a, vk = w in ⟨V (G) \A⟩. Consequently, P ∗ = [v1, v2, ..., vk, b] is an a-b path in ⟨V (G ◦H) \ C⟩. Therefore, ⟨V (G) \ C⟩ is connected. Accordingly, C is an outer-connected hop domi- nating set of G ◦H. Corollary 7. Let G be a connected graph and let H be any graph of orders m and n, respectively. Then γ̃ch(G ◦H) ≤ min {(n+ 1)γ̃c(G),m(pnd(H))}. Proof. Let A be a γ̃c-set in G. By Theorem 9, C = A ∪ (⋃ v∈A V (Hv) ) is an outer-connected hop dominating set in G ◦H. Thus, γ̃ch (G ◦H) ≤ |C| = |A|+ ∑ v∈A |V (Hv)| = (n+ 1)γ̃c(G). Next. let A = ∅ and Sv be a pnd-set of H for each v ∈ V (G). By Theorem 9, C∗ = ⋃ v∈V (G) Sv C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1977 is an outer-connected hop dominating set in G ◦H. Hence, γ̃ch (G ◦H) ≤ |C∗| = ∑ v∈V (G) |Sv| = m(pnd(H)). Therefore, γ̃ch(G ◦H) ≤ min {(n+ 1)γ̃c(G),m(pnd(H))}. Example 1. Consider the corona C4 ◦ P3 in Figure 1. It can be verified that γ̃ch (C4 ◦ P3) = 6 < 8 = |V (C4)| pnd(P3) and γ̃ch (C4 ◦ P3) = 6 < 8 = γ̃c(C4) (|V (P3)|+ 1) . .................................... .................................... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ................................................................................................................. .... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .................................................................................................................. ............ ........... ....... .................................... ............ ........... ....... .................................... .................................... ................................................................................................................ .............................................................................................. .......................................................................................... .............................. .................................... .............................. .................................... .................................... ................................................. ................................................ ............... .................. ................. ................. ................. ................. ........ ........... .......... .......... .......... .......... .......... .......... .......... ......... .............................. .................................... .............................. .................................... .................................... .............................................. ............................................. ............... ................. ................ ................ ................ ................ ........ ........... .......... .......... .......... .......... .......... .......... .......... ..... ............ ........... ....... .................................... ............ ........... ....... .................................... .................................... .......................................................................................................... ......................................................................................... ...................................................................................... • • • • • • Figure 1: The corona C4 ◦ P3 Example 2. Consider the corona of K2 ◦ P3. Then γ̃ch(K2 ◦ P3) = 4 = γ̃c(K2)(|V (P3)|+ 1) = |V (K2)| (pnd(P3)) C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1978 .................................... .................................... .................................... ......................................................................................................................................................................................................................................................................................................................... ..................................................................................................................................................................................................................................................................................... .................................... .................................... .................................... ............................................................................................................................................................................................... ................................................................................... .................................... ............................................... ................................................................................... ............................................................................................................................................... ............ ........... ........... ........... ........... ........... .... ............ ........... ........... ........... ........... ........... ........................................................................... ............................................................................................................ .................................... .................................... ................................................................................... ................................................................................... ........................................................................ ................................................................................... ................................................................................... .................................... ............ ........... ........... ........... ........... ........... ........................................................................... ....................................................................... ............ ........... ........... ........... ........... ........... ....• •• • • ••• Figure 2: The corona K2 ◦ P3 Note that Example 2 shows that the given bound in Corollary 7 cannot be improved. On the other hand, Example 1 shows that strict inequality given in Corollary 7 is attain- able. Theorem 10. Let G and H be connected non-trivial graphs. A subset C = ⋃ x∈S [{x} × Tx] of V (G [H]) is an outer-connected hop dominating set of G [H] if and only if the following conditions hold: (i) S is a hop dominating set of G; and (ii) Tx is a pointwise non-dominating set of H for each x ∈ S with ∣∣N2 G(x) ∩ S ∣∣ = 0. (iii) ⟨(V (G) \ S) ∪ {v ∈ S : Tv ̸= V (H)}⟩ is a connected graph in G. Proof. Suppose C is an outer-connected hop dominating set of G [H] and let W = (V (G) \ S) ∪ {v ∈ S : Tv ̸= V (H)}. Since every outer-connected hop dominating set is a hop dominating set, (i) and (ii) hold by Theorem 2. Let u, v ∈ W where u ̸= v. Suppose u, v ∈ V (G)\S. Let a ∈ V (H). Then (u, a), (v, a) ∈ V (G [H])\C. Since ⟨V (G [H]) \ C⟩ is connected, there exists (u, a)-(v, a) geodesic [(u1, a1), (u2, a2), ..., (uk, ak)], where (u1, a1) = (u, a) and (uk, ak) = (v, a), in ⟨V (G [H]) \ C⟩. Then ui ∈ W for all i ∈ {1, 2, ..., k}. Thus, [u1, ..., uk] is a u-v path in ⟨W ⟩. Suppose u, v ∈ S where Tu ̸= V (H) and Tv ̸= V (H). Let a ∈ V (H) \ Tu and b ∈ V (H)\Tv. Then (u, a), (v, b) ∈ V (G [H])\C. Since ⟨V (G [H]) \ C⟩ is connected, there exists (u, a)-(v, b) geodesic [(u1, a1), ..., (um, am)] , where (u, a) = (u1, a1) and (um, am) = (v, b), in ⟨V (G [H]) \ C⟩. Again, ui ∈ W for all i ∈ {1, 2, ..., k}. Thus, [u1, ..., uk] is a u-v path in ⟨W ⟩. Similarly if u ∈ V (G) \ S and v ∈ S and Tv ̸= V (H), then it can be shown that a u-v path in ⟨W ⟩ exists. Therefore, ⟨W ⟩ is connected. Conversely, suppose that C has the given form and satisfies properties (i), (ii) and (iii). By (i), (ii) and Theorem 2, C is a hop dominating set. Let (u, a), (v, b) ∈ V (G [H]) \ C with (u, a) ̸= (v, b). Consider the following cases. Case 1. u, v ∈ V (G) \ S. Subcase 1.1 u = v. Then a ̸= b. Since H is connected, there exists an a-b path [a1, a2, ..., ak] with a1 = a and ak = b in H. Hence, the path [(u, a1), (u, a2), ..., (u, ak)] is a (u, a)-(v, b) path in ⟨V (G [H]) \ C⟩. Subcase 1.2 u ̸= v. Since u, v ∈ V (G) \ S, there exists a u-v path [u1, u2, ..., uk] where u1 = u and uk = v, in ⟨W ⟩ by (iii). For each i ∈ {2, 3, ..., k − 1}, choose any ai ∈ V (H) if ui ∈ V (G)\S. Oth- erwise let ai ∈ V (H) \ Tuj if uj ∈ S. Then [(u1, a1), (u2, a2), ..., (uk, ak)] where a1 = a and ak = b is a (u, a)-(v, b) path in ⟨V (G [H]) \ C⟩. Hence, the path [(u, a1), (u, a2), ..., (u, ak)] is a (u, a)-(v, b) path in ⟨V (G [H]) \ C⟩. C.J. Saromines, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (4) (2022), 1966-1981 1979 Case 2. u ∈ V (G) \ S and v ∈ S. Then b ∈ V (H) \ Tv. By (iii), a u-v path [u1, u2, ..., up] where u1 = u, up = v exists in ⟨W ⟩. For each i ∈ {2, 3, ..., p− 1}, choose any ai ∈ V (H) if ui ∈ V (G) \ S. Otherwise let ai ∈ V (H) \ Tuj if uj ∈ S. Hence, [(u1, a1), (u2, a2), ..., (up, ap)], where a1 = a, ap = b, is a (u, a)-(v, b) path in ⟨V (G [H]) \ C⟩. Case 3. u, v ∈ S. Then a ∈ V (H)\Tu. and b ∈ V (H)\Tv. Again, by (iii) and by using similar arguments used in Case 1 and Case 2, there exists (u, a)-(v, b) path in ⟨V (G [H] \ C⟩. Accordingly, C is an outer-connected hop dominating set of G [H]. Corollary 8. Let G and H be non-trivial connected graphs such that γ(G) ̸= 1. Then γ̃ch(G [H]) = γth(G) Proof. Let S be a γth-set of G and let p ∈ V (H). Set Tx = {p} for every x ∈ S. Then C = ⋃ x∈S ({x} × Tx) = S × {p} is an outer-connected hop dominating set in G [H] by Theorem 10. Hence γ̃ch (G [H]) ≤ |C| = |S × {p}| = γth(G). Next, let C0 = ∪x∈S0 ({x} ×Rx) be γ̃ch-set of G [H]. Then S0 is a hop dominating set and Rx is a pointwise non-dominating set of H for each x ∈ S0 \N2 G(S0), by Theorem 10 Hence, γ̃ch(G [H]) = |C0| = ∑ x∈S0 |Rx| = ∑ x∈S0∩N2 G(S) |Rx|+ ∑ x∈S\N2 G(S0) |Rx| ≥ ∣∣S0 ∩N2 G(S0) ∣∣+ ∣∣S0 \N2 G(S0) ∣∣ pnd(H). Since H is a non-trivial connected graph, pnd(H) ≥ 2. Thus, by Theorem 3, γ̃ch (G [H]) ≥ γth(G). This establishes the desired equality. 5. Conclusion Outer-connected hop domination, a variant of hop domination, has been introduced and studied for some graphs and graphs resulting from the join, corona and lexicographic REFERENCES 1980 product of two graphs. In the case of the join of graphs, the concept of outer-connected pointwise non-domination plays a vital role. It is recommended that some bounds on the outer-connected hop domination be determined and that the parameter be studied for other graphs. Acknowledgements The authors are very much grateful to the referees for the corrections and suggestions they made in the initial manuscript. This paper had been improved due to the additional inputs and insights the referees had given to the authors. The authors would like to thank the Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP)-Philippines, and MSU-Iligan Institute of Technology for funding this research. References [1] B.D. Acharaya, S. Arumugan, and P.J. Slater. Domination in discrete structures - new directions. AKCE J. Graphs Combin., pages 113–115, 2007. [2] M.H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami. On the outer-conected domination numbers of graphs. Journal of Combinatorial Optimiza- tion, 26(1):10–18, 2013. [3] C. Armada, S. Canoy Jr., and C. Go. Forcing domination numbers of graphs un- der some binary operations. Advances and Applications in Discrete Mathematics, 19(3):213–228, 2018. [4] S. Ayyaswamy, B. Krishnakumari, B. Natarjan, and Y. Venkatakrishnan. Bounds on the hop domination number of a tree. Proceedings-Mathematical Sciences, 125(4):449– 455, 2015. [5] J. Cyman. The outer-conected domination numbers of graphs. Australasian Journal of Combinatorics, 38(1):35–46, 2007. [6] T. Daniel and S. Canoy Jr. Clique domination in graphs. Applied Mathematical Sciences, 9(116):5749–5755, 2015. [7] R. Eballe and S. Canoy Jr. Steiner sets in the join and composition of graphs. Congressus Numerantium, 170:65–73, 2004. [8] S. Omega Espinola and S. Canoy Jr. Restrained locating-domination and restrained differentiating-domination in graphs. International Journal of Mathematics Analysis, 9(45):2243–2255, 2015. [9] T. W. Haynes, S.T. Hedetnieme, and P.J. Slater. Fundamentals of domination in graphs. Monographs and Textbooks in Pure and Applied Mathematics, 28, 1998. REFERENCES 1981 [10] M. Henning and N. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics., 33(4):913–927, 2017. [11] H. Jiang and E. Shan. Outer-conected domination numbers of graphs. American Mathematical Society, 81(1):265–274, 2010. [12] R. Hinampas Jr, J. Hinampas, and A. Dahuman. Independent outer-connected dom- ination in graphs. Global Journal of Pure and Applied Mathematics, 13(1):1–7, 2017. [13] S. Canoy Jr. and S. Arriola. (1, 2)∗-domination in graphs. Advances and Applications in Discrete Mathematics., 18(2):179–190, 2017. [14] S. Canoy Jr., R. Mollejon, and J. G. Canoy. Hop dominating sets in graphs under binary operations. Eur. J. Pure Appl. Math., 12(4):1455–1463, 2019. [15] G. Monsanto and H. Rara. Resolving restrained domination domination in graphs. European Journal of Pure and Applied Mathematics, 14(3):829–841, 2021. [16] C. Natarajan and S. Ayyaswamy. Hop domination in graphs ii. Versita, 23(2):187– 199, 2015. [17] Y. Pabilona and H. Rara. Connected hop domination in graphs under some binary operations. Asian-Eur. J. Math., 11(5):1850075–1–1850075–11, 2018. [18] S. Pacardo and H. Rara. Interior domination in graphs under some binary operations. Applied Mathematical Sciences, 12(14):677–690, 2018. [19] R. Rakim and H. Rara. Total perfect hop domination in graphs under some binary operations. European Journal of Pure and Applied Mathematics, 14(3):803–815, 2021. [20] R. Rakim, H. Rara, and C.J. Saromines. Perfect hop domination in graphs. Applied Mathematical Sciences, 12(13):635–649, 2018.