The Hop Domination Number of Comb Product Graphs

By a graph G = (V, E), we mean a finite undirected connected graph without loops or multiple edges. The order and size of G are denoted by n and m, respectively. For basic graph-theoretic terminology, we refer to [1]. For every vertex v ∈ V, the open neighbourhood N(v) is the set {u ∈ G/uv ∈ E(G)}. The degree of a vertex v ∈ V is deg(v) = |N(v)|. If e = {u, v} is an edge of a graph G with deg(u) = 1 and deg(v) > 1, then we call e a pendant edge or end edge, u a leaf or end vertex and v a support. A vertex of degree n − 1 is called a universal vertex. The distance d(u, v) between two vertices u and v in a connected graph G is the length of a shortest u-v path in G. A u-v path of length d(u, v) is called a u-v geodesic. A vertex x is said to lie on a u-v geodesic P if x is a vertex of P, including the vertices u and v. For two vertices u and v, the closed interval I[u, v] consists of u and v together with all vertices lying on some u-v geodesic. For a set S ⊆ V(G), the interval I_G[S] is the union of all I_G[u, v] for u, v ∈ S.

A set D ⊂ V is a dominating set of G if every vertex v ∈ V − D is adjacent to some vertex in D. A dominating set D is said to be minimal if no subset of D is a dominating set of G. The minimum cardinality of a minimal dominating set of G is called the domination number of G and is denoted by γ(G). The domination number of a graph was studied in [2]. A set S ⊆ V of a graph G is a hop dominating set (hd-set, in short) of G if for every v ∈ V − S, there exists u ∈ S such that d(u, v) = 2. The minimum cardinality of an hd-set of G is called the hop domination number and is denoted by γ_h(G). Any hd-set of order γ_h(G) is called a γ_h-set of G. The hop domination number of a graph was studied in [3–8]. The domination concept has interesting applications in social networks. By applying the hop domination concept, we can improve privacy in social networks.

Let G and H be two connected graphs. Let o be a vertex of H. The comb product of G and H, denoted by G ⊳ H, is the graph obtained by taking one copy of G and |V(G)| copies of H and identifying the i^th copy of H at the vertex o with the i^th vertex of G. By the definition of the comb product, we can say that V(G ⊳ H) = {(a, u): a ∈ V(G), u ∈ V(H)} and (a, u)(b, v) ∈ E(G ⊳ H) whenever a = b and uv ∈ E(H), or ab ∈ E(G) and u = v = o. This concept was studied in [9].

Theorem 2.1. Let H = P_n1 be the path of order n₁ and K = C_n2 be the cycle of order n₂. Then

Proof. Let V(H) = {v₁, v₂, …, v_n1} and V(K) = {u₁, u₂, …, u_n2}. Let V(K_i) = {u_i,1, u_i,2, …, u_i,n2} be the i^th copy of K and u_i,1 (1 ≤ i ≤ n₁) be the root vertex of G = H ⊳ K.

Case 1: 4 ≤ n₂ ≤ 5. Let S be a γ_h-set of G. It is easily observed that each root vertex belongs to S. Then γ_h(G) ≥ n₁. Since S = {u_1,1, u_2,1, u_3,1, …, u_n1,1} is the only γ_h-set of G, γ_h(G) = n₁.

Case 2: n₂ ≥ 6.

Case 2a: n₂ = 6r. Let S = {u_i,1, u_i,4, u_i,7, u_i,10, …, u_i,6r−2}. Then S is a hop dominating set of G, so that γ_h(G) ≤ n₁⌈n₂/3⌉. We have to prove that γ_h(G) = n₁⌈n₂/3⌉. On the contrary, suppose that γ_h(G) ≤ n₁⌈n₂/3⌉ − 1. Then there exists a γ_h-set S′ of G such that |S′| ≤ n₁⌈n₂/3⌉ − 1. Hence there exists an x ∈ V\S′ such that d(x, y) ≥ 3, where y ∈ S′. Therefore S′ is not a hop dominating set of G, which is a contradiction. Hence γ_h(G) = n₁⌈n₂/3⌉.

Case 2b: n₂ = 6r + 1 or 6r + 2 or 6r + 3. Let T = {u_i,1, u_i,4, u_i,10, …, u_i,6r−2} ∪ {u_i,5, u_i,11, …, u_i,6r−1}. Then, as in Case 2a, we can prove that T is a γ_h-set of G, so that γ_h(G) = n₁⌈n₂/3⌉.

Case 2c: n₂ = 6r + 4 or 6r + 5. Let W = {u_i,1, u_i,6, u_i,12, …, u_i,6r} ∪ {u_i,7, u_i,13, …, u_i,6r+1}. Then, as in Case 2a, we can prove that W is a γ_h-set of G, so that γ_h(G) = n₁⌊n₂/3⌋. ∎

Theorem 2.2. Let H = P_n1 be the path of order n₁ ≥ 2 and K = P_n2 be the path of order n₂ ≥ 3. Then

Proof. Let V(H) = {v₁, v₂, …, v_n1} and V(K) = {u₁, u₂, …, u_n2}. Let V(K_i) = {u_i,1, u_i,2, …, u_i,n2} be the i^th copy of K and u_i,1 (1 ≤ i ≤ n₁) be the root vertex of G = H ⊳ K.

Case 1: 1 ≤ n₂ ≤ 3.

Case 1a: n₂ ≥ 3. Then S = {u_1,1, u_2,1, u_3,1, …, u_n1,1} is the only γ_h-set of G, so that γ_h(G) = n₁.

Case 1b: 4 ≤ n₂ ≤ 5. Then S = {u₂, u₃} is the only γ_h-set of G, so that γ_h(G) = 2n₁.

Case 2: n₂ ≥ 6.

Case 2a: n₂ = 6r. Let S = {u_i,3, u_i,9, …, u_i,6r−3} ∪ {u_i,4, u_i,10, …, u_i,6r−2}. Then S is a hop dominating set of G, so that γ_h(G) ≤ n₁⌈n₂/3⌉. We have to prove that γ_h(G) = n₁⌈n₂/3⌉. On the contrary, suppose that γ_h(G) ≤ n₁⌈n₂/3⌉ − 1. Then there exists a γ_h-set S′ of G such that |S′| ≤ n₁⌈n₂/3⌉ − 1. Hence there exists an x ∈ V\S′ such that d(x, y) ≥ 3, where y ∈ S′. Therefore S′ is not a hop dominating set of G, which is a contradiction. Hence γ_h(G) = n₁⌈n₂/3⌉.

Case 2b: n₂ = 6r + 1 or 6r + 2 or 6r + 3. Let T = {u_i,1, u_i,6, u_i,12, …, u_i,6r} ∪ {u_i,7, u_i,13, …, u_i,6r+1}. Then, as in Case 2a, we can prove that T is a γ_h-set of G, so that γ_h(G) = n₁⌈n₂/3⌉.

Case 2c: n₂ = 6r + 4. Let W = {u_i,1, u_i,4, u_i,7, …, u_i,6r+4}. Then, as in Case 2a, we can prove that W is a γ_h-set of G, so that γ_h(G) = n₁(⌈n₂/3⌉ + 1).

Case 2d: n₂ = 6r + 5. Let Z = W ∪ {u_i,6r+5}. Then, as in Case 2a, we can prove that Z is a γ_h-set of G, so that γ_h(G) = n₁(⌈n₂/3⌉ + 1). ∎

Theorem 2.3. Let H and K be two connected graphs. Then γ_h(H ⊳ K) ≤ |V(H)| · γ_h(K).

Proof. Let V(H) = {v₁, v₂, …, v_n1} and V(K) = {u₁, u₂, …, u_n2}. Let V(K_i) = {u_i,1, u_i,2, …, u_i,n2} (1 ≤ i ≤ n₁) be the i^th copy of K. Without loss of generality, let us assume that u_i,1 (1 ≤ i ≤ n₁) is the root vertex of G = H ⊳ K. Let S be a γ_h-set of G. Then γ_h(H ⊳ K) ≤ |V(H)| · |S| = |V(H)| · γ_h(K). ∎

Theorem 2.4. Let H be a connected graph of order n₁ and K be a connected graph of order n₂ with d(K) = 2. Then γ_h(H ⊳ K) = n₁.

Proof. Let V(H) = {v₁, v₂, …, v_n1} and V(K) = {u₁, u₂}. Let V(K_i) = {u_i,1} be the i^th copy of K and u_i,1 (1 ≤ i ≤ n₁) be the root vertex of G = H ⊳ K. We prove that γ_h(G) = n₁. On the contrary, suppose that γ_h(G) ≤ n₁ − 1. Then there exists a γ_h-set S′ of G such that |S′| ≤ n₁ − 1. Hence there exists an x ∈ V\S′ such that d(x, y) ≥ 3, where y ∈ S′. Therefore S′ is not a hop dominating set of G, which is a contradiction. Hence γ_h(H ⊳ K) = n₁. ∎

Theorem 2.5. Let H be any connected graph of order n₁ and K be a connected graph of order n₂ with d(K) = 1. Then

Proof. Let V(H) = {v₁, v₂, …, v_n1} and V(K) = {u₁, u₂}. Let V(K_i) = {u_i,1} be the i^th copy of K and u_i,1 (1 ≤ i ≤ n₁) be the root vertex of G = H ⊳ K.

Case 1: n₁ = 3. Then S = {u_2,1, u_3,1} is the only γ_h-set of G, so that γ_h(G) = 2.

Case 2: n₁ ≥ 4.

Case 2a: n₁ = 4r. Let S = {u_2,1, u_6,1, …, u_4r−2,1} ∪ {u_3,1, u_7,1, …, u_4r−1,1}. Then S is a hop dominating set of G, so that γ_h(G) ≤ ⌈n₁/2⌉. We have to prove that γ_h(G) = ⌈n₁/2⌉. On the contrary, suppose that γ_h(G) ≤ ⌈n₁/2⌉ − 1. Then there exists a γ_h-set S′ of G such that |S′| ≤ ⌈n₁/2⌉ − 1. Hence there exists an x ∈ V\S′ such that d(x, y) ≥ 3, where y ∈ S′. Therefore S′ is not a hop dominating set of G, which is a contradiction. Hence γ_h(G) = ⌈n₁/2⌉.

Case 2b: n₁ = 4r + 1. Let T = S ∪ {u_4r,1}. Then, as in Case 2a, we can prove that T is a γ_h-set of G, so that γ_h(G) = ⌈n₁/2⌉.

Case 2c: n₁ = 4r + 3. Let W = {u_2,1, u_6,1, …, u_4r+2,1} ∪ {u_3,1, u_7,1, …, u_4r+3,1}. Then, as in Case 2a, we can prove that W is a γ_h-set of G, so that γ_h(G) = ⌈n₁/2⌉.

Case 2d: n₁ = 4r + 2. Let W = {u_2,1, u_6,1, …, u_4r−2,1} ∪ {u_3,1, u_7,1, …, u_4r−1,1} ∪ {u_4r,1, u_4r+1,1}. Then, as in Case 2a, we can prove that W is a γ_h-set of G, so that γ_h(G) = ⌈n₁/2⌉ + 1. ∎

Corollary 2.6. Let H = P_n1 be the path of order n₁ and K = K_1,n2 be the star of order n₂. Then

Theorem 2.7. Let H and K be two connected graphs of orders n₁ and n₂, respectively. Then γ_h(H ⊳ K) = 2 if and only if H is K₂ and d(K) ≤ 2.

Proof. Let G = H ⊳ K and γ_h(G) = 2. Hence it follows from Theorem 2.2 that n₁ = 2. Therefore H = K₂. Since γ_h(G) = 2, S = V(H). Let V(K) = {u₁, u₂, …, u_n2} and V(K_i) = {u_i,1, u_i,2, …, u_i,n2} (1 ≤ i ≤ n₁) be the i^th copy of K. We have to prove that d(K) ≤ 2. On the contrary, suppose that d(K) ≥ 3. Let P: x₁, x₂, …, x_k (k ≥ 3) be a diametral path in K and P_i: x_i,1, x_i,2, …, x_i,k (1 ≤ i ≤ n₂) be a diametral path in K_i. Then there exists x_ij′ ∈ V(P_i) such that either d(x, x_ij′) ≥ 3 or d(y, x_ij′) ≥ 3, which is a contradiction. Therefore d(K) ≤ 2. ∎

Corollary 2.8. Let H and K be two connected graphs of orders n₁ and n₂, respectively. Then γ_h(H ⊳ K) = 2 if and only if H is K₂ and K is K_1,n2. ∎

Corollary 2.9. Let H and K be two connected graphs of orders n₁ and n₂, respectively. Then γ_h(H ⊳ K) = 2 if and only if H is K₂ and K is either C₃ or C₄ or C₅. ∎

Theorem 2.10. Let H be a connected graph of order n₁ and K be a connected graph of order n₂ with d(K) ≥ 3. Then S ⊆ V(K_i) for all i (1 ≤ i ≤ n₂).

Proof. We prove that S ⊆ V(K_i) for all i (1 ≤ i ≤ n₂). On the contrary, suppose that S ⊄ V(K_i) for all i (1 ≤ i ≤ n₂). Let P: x₁, x₂, …, x_k (k ≥ 3) be a diametral path in K and P_i: x_i,1, x_i,2, …, x_i,k (1 ≤ i ≤ n₂) be a diametral path in K_i. If S ⊆ V(H), then there exists an x_ij ∈ K_i such that d(S, x_ij) ≥ 3, which is a contradiction. Hence S ⊆ V(K_i) for all i (1 ≤ i ≤ n₂). ∎