Locating-domination in a graph, a variation of the standard domination, was defined by Slater et al. in [13] and [14]. For protection of a certain system or network, the problem of determining the location of monitoring devices (e.g. fire alarms or cameras) so as to identify the exact location of an intruder (e.g. fire, burglar) when a problem at a facility or system arises can be modelled by this concept. This parameter and some of its variations had been studied in [2], [3], [6], [7], and [8].

In 2015, Natarajan and Ayyaswamy [10] introduced and studied the concept of hop domination in a graph. This concept and some of its variations were also studied in [1], [4], [9], and [12].

Apart from other possible applications of the concept of locating-hop domination similar to those of the standard locating-domination, the concept can also be used for a social network application. For example, consider a certain company with a large number of employees and suppose the company's president decides to form an internal committee of evaluators to do an assessment of the employees' job performance and productivity for management purpose. To minimize possible biases that may occur in the process, it is imposed that an evaluator should neither be a close friend nor an enemy to any employee (an individual outside this committee) under his or her evaluation list and that no two employees are evaluated by exactly the same set of evaluators from the committee. Also, to save time, an employee needs to be evaluated by a nearest non-biased evaluator. Since these criteria may still allow at most one employee (a non-evaluator) to be unevaluated or unassessed, it is further imposed that every employee outside the committee must go through the evaluation process, i.e., nobody is left out unevaluated. To model this evaluation process, a social network can be constructed, where each employee (including members of the committee) is represented by a vertex and an edge between two employees is formed if the they are either close friends or enemies. With respect to this network, the first set of imposed guidelines in the aforementioned evaluation process would actually require that the set of evaluators satisfies the 'locating-hop' condition. The additional imposed guideline (to ensure completeness of the evaluation process) would necessitate that the set of evaluators is a 'hop dominating' set. This social network application is a slight modification of the one given by Desormeaux et al. in [5] for non-dominating sets in graphs.

In this paper, we define and do an initial study of the concept of locating-hop dominating set in a graph. As formally defined in a bit and as implicitly mentioned earlier, a locating-hop set is 'almost' a hop dominating set as it may allow at most a vertex outside the set to be 'hop undominated'. In a portion of this paper, one may find a result (a result that deals with the concept of locating-hop dominating on a disconnected graph) that does not hold when the condition 'locating-hop dominating set' is replaced by just 'locating hop set'. This somehow also makes 'locating-hop dominating set' a bit interesting concept to define and study.

Let G be a simple graph with vertex-set V(G) and edge-set E(G). For any two vertices u,v ∈ V(G), the distance d_G(u,v) between u and v is the length of a shortest u-v path in G. Any u-v path of length equal to d_G(u,v) is called a geodesic (u-v godesic). Two vertices u and v are neighbors (sometimes adjacent) if uv∈E(G). The set of neighbors of a vertex u of G, denoted by N_G(u), is called the open neighborhood of u in G. The closed neighborhood of u is the set NG[u]=NG(u)∪{u}. The open neighborhood of X⊆V(G) is the set NG(X)=∪ u∈XNG(u) and its closed neighborhood is the set NG[X]=NG(X)∪X. The open hop neighborhood of u in G, denoted by N_G(u,2), is the set given by NG(u,2)={w∈V(G):dG(u,w)=2} and its closed hop neighborhood is NG[u,2]=NG(u,2)∪{u}. The open hop neighborhood of S⊆V(G) is the set NG(S,2)=∪ u∈SNG(u,2) and its closed hop neighborhood is the set NG[S,2]=NG(S,2)∪S. The degree of vertex u in G, denoted by degG(u), is equal to |N_G(u)|.

A set S⊆V(G) is a locating set of G if for any two distinct vertices v,w∈V(G)∖S, NG(v)∩S≠NG(w)∩S. A locating set S is a locating-dominating set of G if NG(v)∩S≠∅ for each v∈V(G)∖S. The smallest cardinality of a locating (resp. locating-dominating) set of G is denoted by ln(G) (resp. γL(G)). Any locating (resp. locating-dominating) set of G with cardinality ln(G) (resp. gammaL(G)) is called a ln-set (resp. γ_L-set) of G. We also point out that a locating set is 'nearly' or 'almost' a dominating set because it may allow at most a vertex in V(G)∖S to be undominated. A study of the concept of locating set can also be found in [11].

A subset S of V(G) is called a hop dominating set of G if NG[S,2]=V(G), that is, for every v∈V(G)∖S, there exists u ∈ S such that dG(u,v)=2. The minimum cardinality of a hop dominating set of G, denoted by γ_h(G), is called the hop domination number of G. Any hop dominating set of G with cardinality γ(G) is called a γ_h-set of G.

A subset S of G is a locating-hop set of G if NG(u,2)∩S≠NG(v,2)∩S for every two distinct vertices u and v of V(G)∖S. A locating-hop set of G which is also a hop dominating set is called a locating-hop dominating set. The minimum cardinality of a locating-hop dominating set of G, denoted by γlh(G), is called the locating-hop domination number of G.

A set S⊆V(G) is a complement-locating set of G (or a locating set of G¯) if for any two distinct vertices v,w∈V(G)∖S, NG¯(v)∩S=[V(G)∖NG(v)]∩S≠[V(G)∖NG(w)]∩S=NG¯(w)∩S. A complement-locating set S of G is called a complement locating-dominating set of G (or a locating-dominating set of G¯) if for each v∈V(G)∖S, [V(G)∖NG(v)]∩S=N G¯(v)∩S≠∅. The smallest cardinality of a complement-locating (resp. complement locating-dominating) set of G is denoted by cln(G) (resp. cldn(G)). Any complement-locating (resp. complement locating-dominating) set of G with cardinality cln(G) (resp. cldn(G)) is called a cln-set (resp. a cldn-set) of G. Clearly, cln(G)=ln(G¯) and cldn(G)=γL(G¯).

Since any set S of size s has 2^s distinct subsets, it is easily observed from the definition that if S is locating-hop dominating of a graph G on n vertices, then the inequality 2s>n−s is satisfied. We state this formally as a simple result.

Lemma 2.1. Let G be a connected graph on n vertices. If S is a locating-hop dominating set of G and s = |S|, then n<2s+s.

Proposition 2.2. Let G be a connected graph on n vertices. Then 1≤γlh(G)≤n. Moreover,

• (i) γ_lh (G)=1 if and only if G is the trivial graph;

• (ii) γ_lh (G)= n if and only if G=K_n.
  

Proof. Clearly, 1≤γlh(G)≤n.

(i) Suppose γlh(G)=1, say S={u} is a γlh-set of G. If G is a nontrivial connected graph, then there exists v∈V(G)∩NG(u). This implies that S is not a hop dominating set of G, a contradiction. Therefore, G is the trivial graph. Clearly, if G is the trivial graph, then γlh(G)=1.

(ii) Suppose γlh(G)=n and suppose further that G≠Kn. Then there exist distinct vertices v,w∈V(G) such that dG(v,w)=2. Let S=V(G)∖{v}. Then S is a locating hop dominating set of G. Hence, γlh(G)≤|S|=n−1, a contradiction. Therefore, G = K_n. The converse is clear.

Proposition 2.3. Let G be a connected graph of order n. If γlh(G)=2, then 2≤n≤5. Moreover,

• (i) if n=2,3, then G = P₂ and G = P₃, respectively;

• (ii) if n = 4, then G = P₄ or G = C₄; and
  

• (iii) if n = 5, then G= C₅ or G is (isomorphic to) the graph obtained from a cycle C₅ = [v₁,v₂,v₃,v₄,v₅, v₁] by adding the edge v₃v₅, or G is (isomorphic to) the graph obtained from a cycle C₅ = [v₁,v₂,v₃,v₄,v₅, v₁] by adding the edge v₃v₅ and removing the edge v₁v₂.
  

Proof. Suppose that γlh(G)=2 and let S={v1,v2} be a γlh-set of G. Clearly, n≥2. By Lemma 2.1, n≤5. Hence, 2≤n≤5.

Clearly, (i) holds. Suppose n = 4. Let a,b∈V(G)∖S. Since S is a hop dominating set, we may assume without loss of generality that v1∈NG(a,2)∩S. Suppose that [a,x,v₁] is an a-v₁ geodesic. If x = v₂, then v1v2∈E(G). It follows that NG(a,2)∩S={v1}. Since S is a locating hop dominating set, NG(b,2)∩S={v2} or NG(b,2)∩S={v1,v2}. Suppose NG(b,2)∩S≠{v2}. Then NG(b,2)∩S={v1,v2}. This implies that ab ∈ E(G). Since dG(a,v2)=dG(v1,v2)=1, it follows that dG(b,v1)=3, a contradiction. Therefore, NG(b,2)∩S={v2}. Thus, G is [b,a,v2,v1] or [b,v1,v2,a] or [b,a,v2,v1,b]. Suppose now that x = b. Then this forces NG(b,2)∩S={v2} because S is a hop dominating set. If v1v2∉E(G), then av2∈E(G) and NG(a,2)∩S={v1}. It follows that G=[v1,b,a,v2]=P4. Suppose v1v2∈E(G). Then G is [a,b,v₁,v₂] or [a,b,v₁,v₂,a]. Therefore, G = P₄ or G = C₄, showing that (ii) holds.

Next, suppose that n = 5. Let v3,v4,v5∈V(G)∖S. Since S is a locating hop dominating set, we may assume that NG(v3,2)∩S={v1}, NG(v5,2)∩S={v2}, and NG(v4,2)∩S={v1,v2}. Suppose first that v1v2∈E(G). Since NG(v4,2)∩S={v1,v2}, v1v4,v2v4∉E(G). It follows that v3v4,v4v5,v2v3,v1v5∈E(G). If v3v5∉E(G), then G=[v1,v2,v3,v4,v5,v1]=C5. If v3v5∈E(G), then G is the graph obtained from the cycle [v1,v2,v3,v4,v5,v1] by adding the edge v₃v₅. Suppose that v1v2∉E(G). Again, it can be shown that v3v4,v4v5,v2v3,v1v5∈E(G). Moreover, since NG(v3,2)∩S={v1} and NG(v5,2)∩S={v2}, it follows that v3v5∈E(G). Thus, G is the graph obtained from the cycle C5=[v1,v2,v3,v4,v5,v1] by adding the edge v₃v₅ and removing the edge v₁v₂. This proves (iii).

Theorem 2.4. Let G1,G2,…,Gk be the distinct components of G, where k ≥ 2. Then S is a locating hop dominating set of G if and only if Sj=S∩V(Gj) is a locating-hop dominating set of G_j for each j∈{1,2,…,k}.

Proof. Suppose S is locating-hop dominating set of G and let j∈{1,2,…,k}. Let v∈V(Gj)∖Sj. Since v∉S and S is a hop dominating set, there exists w ∈ S such that v∈NG(w,2). This implies that w ∈ S_j and v∈NGj(w,2). This shows that S_j is a hop dominating set of G_j. Next, let a,b∈V(Gj)∖Sj where a ≠ b. Since S is locating-hop set

NGj(a,2)∩Sj=NG(a,2)∩S≠NG(b,2)∩S=NGj(b,2)∩Sj.

Thus, S_j is a locating-hop dominating set of G_j for each j∈{1,2,…,k}.

For the converse, suppose that Sj=S∩V(Gj) is a locating-hop dominating set of G_j for each j∈{1,2,…,k}. Then clearly, S is a hop dominating set of G. Let v,w∈V(G)∖S with v≠w and let G_i and G_j be the components of G with v∈V(Gi)∖Si and w∈V(Gj)∖Sj. Since S_i and S_j are locating-hop sets (where it may happen that i = j),

NG(a,2)∩S=NGi(v,2)∩Si≠NGj(w,2)∩Sj=NG(w,2)∩S.

Therefore, S is a locating-hop set of G.

It is worth mentioning that Theorem 2.4 does not hold if 'locating-hop dominating' is replaced by 'locating-hop'. Indeed, if there are two distinct locating sets S_j and S_k which have each a single vertex in V(Gj)∖Sj and V(Gk)∖Sk, respectively, that are not hop-dominated in the respective components, then the set S cannot be a locating hop set of G.

The next result follows from Theorem 2.4.

Corollary 2.5. Let G1,G2,…,Gk be the distinct components of G. Then γlh(G)=∑ j=1kγlh(Gj).

As an immediate consequence of Proposition 2.2(ii) and Theorem 2.4, we have the next result.

Corollary 2.6. Let G be a graph of order n. Then γlh(G)=n if and only if every component of G is complete. In particular, γlh(Kn)=γlh( K¯n)=n.

The next result is a general version (it includes disconnected graphs) of the one given in [11].

Theorem 2.7. Let G be graph of order n≥2. Then the following statements hold.

• (i) 1 ≤ ln(G) ≤ n-1 and ln(G) = 1 if and only if G ∈{K₂, øverline{K₂}, P₃, K₁ ∪ K₂}.
  

• (ii) ln(G) = n- 1 if and only if G = K_n or G=K¯n.
  

From the preceding result and the fact that cln(G)=ln(G¯), we get the next result.

Corollary 2.8. Let G be graph of order n≥2. Then the following statements hold.

• (i) 1≤cln(G)≤n−1 and cln(G)=1 if and only if G∈{K2,K2¯,P3,K1∪K2}.
  

• (ii) cln(G) = n- 1 if and only if G = K_n or G=K¯n.
  

The following relationship is obtained in [2].

Theorem 2.9. Let G be a connected graph of order n≥2. If ln(G)<γL(G), then γL(G)=ln(G)+1.

It should be noted that Theorem 2.9 also holds for disconnected graphs. Hence, the next result is immediate.

Corollary 2.10. Let G be a graph of order n≥2. If cln(G)<cldn(G), then cldn(G)=γL(G¯)=ln(G¯)+1=cln(G)+1.

The join 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)=E(G)∪E(H)∪{uv:u∈V(G),v∈V(H)}.

Theorem 2.11. Let G and H be any two graphs. Then S⊆V(G+H) is a locating-hop dominating set of G+H if and only if S=SG∪SH where S_G and S_H are complement locating-dominating sets of G and H (locating-dominating sets of G¯ and H¯ ), respectively.

Proof. Suppose that S is a locating-hop dominating set of G+H. Let SG=V(G)∩S and SH=V(H)∩S. Since S is a hop dominating set of G+H, SG≠∅ and SH≠∅. If S_G = V(G), then it is a complement locating-dominating set of G. Suppose SG≠V(G) and let v∈V(G)∖SG. Since S is a hop dominating set, there exists w ∈ S such that dG+H(w,v)=2. Hence, w∈SG∖NG(v). Next, let x,y∈V(G)∖SG where x ≠ y. Since S is a hop locating set, [V(G)∖NG(x)]∩SG=NG+H(x,2)∩S≠NG+H(y,2)∩S=[V(G)∖NG(y)]∩SG, showing that S_G is a complement-locating set of G. Thus, S_G is a complement locating-dominating set of G. Similarly, S_H is a complement locating-dominating set of H.

For the converse, suppose that S=SG∪SH where S_G and S_H are complement locating-dominating sets of G and H, respectively. Let v∈V(G+H)∖S. Suppose v∈V(G)∖SG. Then by assumption, there exists z∈SG∖NG(v). It follows that dG+H(z,v)=2. Similarly, if v∈V(H)∖SH, then there exists w∈SH such that that dG+H(w,v)=2. This shows that S is a hop dominating set of G+H. Now let a,b∈V(G+H)∖S where a ≠ b. Suppose that a,b∈V(G)∖SG. Since S_G is a complement-locating set of G, NG+H(a,2)∩S=[V(G)∖NG(a)]∩SG≠[V(G)∖NG(b)]∩SG=NG+H(b,2)∩S. Similarly, NG+H(a,2)∩S=[V(H)∖NH(a)]∩SH≠[V(H)∖NH(b)]∩SH=NG+H(b,2)∩S if a,b∈V(H)∖SH. Suppose now that a∈V(G)∖SG and b∈V(H)∖SH. Then NG+H(a,2)∩S=[V(G)∖NG(a)]∩SG≠[V(H)∖NG(a)]∩SH=NG+H(b,2)∩S. Therefore, S is a locating-hop dominating set of G+H.

Corollary 2.12. Let G be a graph and let n be a positive integer. Then S⊆V(Kn+G) is a locating hop dominating set of K_n+G if and only if S=V(Kn)∪SG where S_G is a complement locating-dominating set of G.

Proof. The only complement locating-dominating set of K_n is V(K_n). Thus, by Theorem 2.11, the result follows.

The next results follow directly from Theorem 2.11 and Corollary 2.12.

Corollary 2.13. Let G and H be any two graphs. Then γlh(G+H)=cldn(G)+cldn(H)=γL(G¯)+γL(H¯).

Corollary 2.14. Let G be a graph and let n be a positive integer. Then γlh(Kn+G)=n+γL(G¯).

The corona of graphs G and H, denoted by G∘H, is the graph obtained from G by taking a copy H^v of H and forming the join 〈v〉+Hv=v+Hv for each v ∈ V(G).

Theorem 2.15. Let G be a non-trivial connected graph and let H be any graph. Then S⊆V(G∘H) is a locating-hop dominating set of G∘H if and only if S=A∪[∪v∈V(G)Dv] where

• (i) A⊆V(G) such that for any two distinct vertices v,w∈V(G)∖A, NG(v)≠NG(w) or NG(v,2)∩A≠NG(w,2)∩A;
  

• (ii) D_v is a complement-locating set of H^v for each v∈V(G)∖NG(A);
  

• (iii) D_v is a complement locating-dominating set of H^v for each v ∈ V(G) ∖ N_G(A);
  

• (iv) D_w is a dominating set of H^w for each w ∈ V(G) such that N_G(v) = {w} for some v∈V(G)∖A and NG(w)∩A=∅; and
  

• (v) if D_v is not a complement locating-dominating set of H^v for some v ∈ V(G), then D_w is a complement locating-dominating set of H^w for each w ∈ V(G) ∖ {v} with N_G(w) ∩ A = N_G(v) ∩ A.
  

Proof. Suppose S is a locating-hop dominating set of G∘H. Let A=S∩V(G) and let Dv=S∩V(Hv) for each v∈V(G). Then S=A∪[∪v∈V(G)Dv]. Let v,w∈V(G)∖A with v≠w. Since S is a hop-locating set,

[NG(v,2)∩A]∪[∪x∈NG(v)Dx]=NG∘H(v,2)∩S            ≠NG∘H(w,2)∩S            =[NG(w,2)∩A]∪[∪y∈NG(w)Dy].

This implies that NG(v,2)∩A≠NG(w,2)∩A or NG(v)≠NG(w), showing that (i) holds.

Next, let v∈V(G) and let a,b∈V(Hv)∖Dv with a≠b. Since S is a locating-hop set,

([V(Hv)∖NHv(a)]∩Dv)∪[NG(v)∩A]=NG∘H(a,2)∩S≠NG∘H(b,2)∩S=([V(Hv)∖NHv(b)]∩Dv)∪[NG(v)∩A].

Hence,

[V(Hv)∖NHv(a)]∩Dv≠[V(Hv)∖NHv(b)]∩Dv.

This shows that D_v is a complement-locating set of H^v. Hence, (ii) holds. Suppose v∈V(G)∖NG(A). Since S is a hop dominating set, D_v must be a complement locating-dominating set of H^v, showing that (iii) holds. To show (iv), suppose that w ∈ V(G) such that NG(v)={w} for some v∈V(G)∖A and NG(w)∩A=∅. If Dw=V(Hw), then we are done. So suppose Dw≠V(Hw) and let q∈V(Hw)∖Dw. Then by assumption and the fact that S is a locating-hop set,

Dw=NG∘H(v,2)∩S≠NG∘H(q,2)∩S=[V(Hw)∖NH(q)]∩Dw.

This implies that NH(q)∩Dw≠∅. This shows that D_w is a dominating set of H^w. Again, since S is a locating-hop set G∘H, (v) also holds.

For the converse, suppose that S is as described and satisfies properties (i)-(v). Let x∈V(G∘H)∖S and let v∈V(G) such that x∈V(v+Hv). Suppose x = v. Then v∉A. Let w∈V(G)∩NG(v). Pick any y∈Dw. Then y∈S∩NG∘H(v,2). Suppose x ≠ v. Then x∈V(Hv)∖Dv. If NG(v)∩A≠∅, say u∈NG(v)∩A, then u∈S∩NG∘H(x,2). If NG(v)∩A=∅, then there exists z∈[V(Hv)∖NHv(x)]∩Dv by property (iii). Hence, there exists z∈S∩NG∘H(x,2). This shows that S is a hop dominating set of G∘H.

Now let a,b∈V(G∘H)∖S with a ≠ b and let v,w∈V(G) such that a∈V(v+Hv) and b ∈ V(w + H^w). Consider the following cases:

Case 1: v = w

Suppose a,b∈V(Hv)∖Dv. By (ii) and (iii), D_v is a complement locating-dominating set of H^v. Consequently, NG∘H(a,2)∩S≠NG∘H(b,2)∩S. Suppose a = v and b∈V(Hv)∖Dv. Pick any z ∈ N_G(v). Since Dz⊆NG∘H(a,2)∖NG∘H(b,2), it follows that NG∘H(a,2)∩S≠NG∘H(b,2)∩S.

Case 2: v≠w

Suppose a = v and b = w. Then v,w∈V(G)∖A. By property (i), NG(v)≠NG(w) or NG(v,2)∩A≠NG(w,2)∩A. If NG(v,2)∩A≠NG(w,2)∩A, then NG∘H(a,2)∩S≠NG∘H(b,2)∩S. Suppose NG(v)≠NG(w). We may assume that that there exists p∈NG(v)∖NG(w). Then Dp⊆NG∘H(a,2)∖NG∘H(b,2). Hence, NG∘H(a,2)∩S≠NG∘H(b,2)∩S.

Next, suppose that a = v and b∈V(Hw)∖Dw (or b = w and a∈V(Hv)∖Dv). If |NG(v)|>1 or vw∉E(G), pick any z∈NG(v)∖{w}. Then Dz⊆NG∘H(a,2)∖NG∘H(b,2). It follows that NG∘H(a,2)∩S≠NG∘H(b,2)∩S. Suppose that NG(v)={w}. If NG(w)∩A≠∅, then NG∘H(a,2)∩S≠NG∘H(b,2)∩S because NG(w)∩A⊆NG∘H(b,2)∖NG∘H(a,2). If NG(w)∩A=∅, then D_w is a dominating set of of H^w by (iv). Hence, NG∘H(a,2)∩S≠NG∘H(b,2)∩S.

Finally, suppose that a∈V(Hv)∖Dv and b∈V(Hw)∖Dw. If [V(Hv)∖NHw(a)]∩Dv≠∅ and [V(Hw)∖NHw(b)]∩Dw≠∅, then NG∘H(a,2)∩S≠NG∘H(b,2)∩S. Suppose one, say [V(Hv)∖NHw(a)]∩Dv=∅. If NG(v)∩A≠NG(w)∩A, then NG∘H(a,2)∩S≠NG∘H(b,2)∩S. If NG(v)∩A=NG(w)∩A, then [V(Hw)∖NHw(b)]∩Dw≠∅ by (v). Thus, NG∘H(a,2)∩S≠NG∘H(b,2)∩S.

Accordingly, S is a locating-hop dominating set of G∘H.

The lexicographic product of graphs G and H, denoted by G[H], is the graph with vertex set V(G[H])=V(G)×V(H) such that (v,a)(u,b)∈E(G[H]) if and only if either uv∈E(G) or u = v and ab∈E(H).

Note that every non-empty subset C of V(G)×V(H) can be expressed as C=∪x∈S[{x}×Tx], where S⊆V(G) and Tx⊆V(H) for each x∈S.

Theorem 2.16. Let G and H be non-trivial connected graphs. Then C=∪ x∈S[{x}×Tx ], where S⊆V(G) and

Tx⊆V(H) for each x∈S, is a locating-hop dominating set of G[H] if and only if the following conditions hold:

• (i) S = V(G)

• (ii) T_x is a complement-locating set of H for all x∈S.
  

• (iii) If T_x is not complement locating-dominating for some x∈S, then T_y is complement locating-dominating for all y ∈ S ∖ {x} with N_G(x,2) = N_G(y,2).
  

• (iv) T_x is a complement locating-dominating set of H for each x ∈ S ∖ N_G(S,2).
  

Proof. Suppose C is a locating-hop dominating set of G[H]. Suppose there exists z∈V(G)∖S. Pick distinct vertices a,b ∈ V(H). Then (z,a),(z,b)∈V(G[H])∖C and NG[H]((z,a))∩C= ∪ x∈ NG (z,2)∩S [{x}×Tx]=NG[H]((z,b))∩C. This implies that C is not a locating-hop set, contrary to our assumption. Thus, S = V(G), showing that (i) holds.

Now let x∈S. Let p,q∈V(H)∖Tx with p ≠ q. Then (x,p),(x,q)∈V(G[H])∖C. Now, NG[H]((x,p),2)∩C=[{x}×(V(H)∖NH(p))]∩({x}×Tx)∪[∪w∈NG(x,2)({w}×Tw)] and NG[H]((x,q),2)∩C=[{x}×(V(H)∖NH(q))]∩({x}×Tx)∪[∪w∈NG(x,2)({w}×Tw)]. Since C is a locating-hop set, [{x}×(V(H)∖NH(p))]∩({x}×Tx)≠[{x}×(V(H)∖NH(q))]∩({x}×Tx). This implies that (V(H)∖NH(p))∩Tx≠(V(H)∖NH(q))∩Tx. Hence, T_x is a complement-locating set of H, showing that (ii) holds. Suppose there exists x such that T_x is not complement locating-dominating and let y∈S∖{x} with NG(x,2)=NG(y,2). Let p∈V(H)∖Tx be such that [V(H)∖NH(p)]∩Tx=∅ and let q∈V(H)∖Ty. Since C is a locating-hop dominating set, NG(x,2)=NG(y,2), and [V(H)∖NH(p)]∩Tx=∅, it follows that [V(H)∖NH(q)]∩Ty≠∅. This implies that T_y is a complement locating-dominating set of H, showing that (iii) holds.

Next, let x∈S∖NG(S,2). If T_x = V(H), then T_x is a complement locating-dominating set of H. So suppose that Tx≠V(H) and let t∈V(H)∖Tx. Since C is hop dominating and (x,t)∉C, there exists (w,s)∈C such that dG[H]((x,t),(w,s))=2. The condition x∈S∖NG(S,2) would imply that w = x and s∈[V(H)∖NH(t)]∩Tx. Hence, T_x is a complement locating-dominating set of H, showing that (iv) holds.

For the converse, suppose that C satisfies properties (i)-(iv). Let (x,a)∈V(G[H])∖C. Then a∈V(H)∖Tx. If x∈NG(S,2), then there exists z∈NG(x,2). Let b ∈ T_z. Then (z,b)∈C∩NG[H]((x,a),2). Suppose x∈S∖NG(S,2). By (iv), T_x is a complement locating-dominating set of H. Hence, there exists p∈[V(H)∖NH(a)]∩Tx. This implies that (x,p)∈C∩NG[H]((x,a),2). Therefore, C is a hop dominating set of G[H].

Next, let (v,q),(w,s)∈V(G[H])∖C with (v,q)≠(w,s). Then

NG[H]((v,q),2)∩C=[{v}×(V(H)∖NH(q))]∩({v}×Tv)∪[∪ z∈ NG(v,2)[{z}×Tz],

and

NG[H]((w,s),2)∩C=[{w}×(V(H)∖NH(s))]∩({w}×Tw)∪[∪ y∈ NG(w,2)[{y}×Ty].

Consider the following cases:

Case 1: v = w

Then q,s∈V(H)∖Tv with q ≠ s. By (ii), T_v is a complement-locating set; hence, [V(H)∖NH(q)]∩Tv≠[V(H)∖NH(s)]∩Tv. It follows that NG[H]((v,q),2)∩C≠NG[H]((v,s),2)∩C.

Case 2: v ≠ w

Then q∈V(H)∖Tv and s∈V(H)∖Tw. If NG(v,2)≠NG(w,2), then clearly, NG[H]((v,q),2)∩C≠NG[H]((w,s),2)∩C. Suppose NG(v,2)=NG(w,2). If T_v and T_w are both complement locating-dominating sets, then NG[H]((v,q),2)∩C≠NG[H]((w,s),2)∩C. Suppose T_v is not complement locating-dominating. Then T_w is complement locating-dominating by (iii). It follows that NG[H]((v,q),2)∩C≠NG[H]((w,s),2)∩C.

Accordingly, C is a locating-hop dominating set of G[H].

A connected graph G is distance-two point determining if NG(x,2)≠NG(y,2) for any distinct vertices x,y∈V(G).

Note that P₄, C₄, and the star K_1,n, where n ≥ 2, are distance-two point determining.

Corollary 2.17. Let G and H be non-trivial connected graphs. Then γlh(G[H])≤|V(G)|cldn(H)=|V(G)|γL(H¯). If G is distance-two point determining and γ(G)≠1, then γlh(G[H])=|V(G).|cln(H)=|V(G)|.ln(H¯).

Proof Let S = V(G) and let T_x be a cldn-set of H for each x ∈ V(G). By Theorem 2.16, C=∪ x∈S[{x}×Tx ] is a locating-hop dominating set of G[H]. It follows that γlh(G[H])≤|C|=|V(G)|cldn(H).

Next, suppose that G is distance-two point determining and γ(G)≠1. Let S' = V(G) and let R_x be a cln-set of H for each x ∈ S. Since γ(G)≠1, x∈NG(S,2) for each x ∈ S. Thus, by Theorem 2.16, γlh(G[H])≤|C|=|V(G)|.cln(H)C= ∪ x∈S′ [{x}×Rx] is a locating-hop dominating set of G[H]. It follows that γlh(G[H])≤|C|=|V(G)|.cln(H). Now, if C0= ∪ x∈S 0 [{x}×Tx] is a γ_lh-set of G[H], then S₀ = V(G) and T_x is a complement-locating set of H for each x ∈ V(G) by Theorem 2.16. Hence, γlh(G[H])=|C0|=∑ x∈S 0|Tx|≥|V(G)|.cln(H). Therefore, γlh(G[H])=|V(G)|.cln(H).

Corollary 2.18. Let G and H be non-trivial connected graphs. If G is distance-two point determining and γ(G)=1, then γlh(G[H])=cldn(H)+(|V(G)|−1)cln(H).

Proof. Let DG=v∈V(G):v   is a dominating set of   G. Since G is distance-two point determining, it follows that |D_G| =1. Set S = V(G). Let T_v be a cldn-set of H for v ∈ D_G and let T_x be a cln-set of H for each x∈V(G)∖{v}. Then, by Theorem 2.16, C=[∪ x∈S∖{v}({x}×Tx)]∪({v}×Tv) is a locating-hop dominating set of G[H]. Hence, γlh(G[H])≤|C|=cldn(H)+(|V(G)|−1)cln(H).

Suppose now that C*=[∪ x∈S * ({x}×Rx)] is a γlh-set of G[H]. Again, there exists a unique vertex v such that {v} is a dominating set of G. By Theorem 2.16, S^*= V(G), R_v is a complement locating-dominating set and R_x is a complement-locating set of H for each x∈V(G)∖{v}. Thus, γlh(G[H])=|C*|=|Rv|+∑ x∈S * ∖{v}|Rx|≥cldn(H)+(|V(G)|−1)cln(H). Therefore, γlh(G[H])=cldn(H)+(|V(G)|−1)cln(H) as asserted.

Corollary 2.19. Let G be a non-trivial connected distance-two point determining graph and let p ≥ 2 be a positive integer.

γlh(G[Kp])=|V(G)|(p−1) if γ(G)≠1(p−1)|V(G)|+1 if γ(G)=1,

Proof. Suppose first that γ(G)≠1. By Corollary 2.18 and the fact that cln(Kp)=ln( K¯p=p−1, it follows that γlh(G[Kp])=|V(G)|(p−1).

Next, suppose that γ(G) = 1. By Corollary 2.18 and the fact that cldn(Kp)=γL K¯p=p, we have γlh(G[Kp])=p+(p−1)(|V(G)|−1)=(p−1)|V(G)|+1.

Corollary 2.20. Let H be a non-trivial connected graph and let p ≥ 2 be a positive integer. Then γlh(Kp[H])=p.cldn(H).

Proof. Let G = K_p. Then v is a dominating vertex of G for each v ∈ V(G). Thus, if C0= ∪ z∈S 0 [{z}×Tz] is a γ_lh-set of G[H], then S₀ = V(G) and each T_z is a cldn-set of H by Theorem 2.16. Consequently, γlh(Kp[H])=p.cldn(H).