Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17 https://doi.org/10.1007/s12044-018-0395-2

2-Domination number of generalized Petersen graphs DAVOOD BAKHSHESH, MOHAMMAD FARSHI∗ and MOHAMMAD REZA HOOSHMANDASL Department of Computer Science, Combinatorial and Geometric Algorithms Laboratory, Yazd University, Yazd, Iran *Corresponding author. E-mail: [email protected]; [email protected]; [email protected]

MS received 9 December 2015; revised 11 August 2016; accepted 20 June 2017 Abstract. Let G = (V, E) be a graph. A subset S ⊆ V is a k-dominating set of G if each vertex in V − S is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs P(5k + 1, 2) and P(5k+2, 2), for k > 0, is 4k+2 and 4k+3, respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and P(5k+4, 3). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3). Keywords. number.

Generalized Petersen graph; k-domination number; α-domination

2010 Mathematics Subject Classification.

05C69.

1. Introduction Let G be a simple, finite and undirected graph with vertex set V . A set S ⊆ V is a kdominating set in G if every vertex in V − S has at least k neighbors in S, that is, for each v ∈ V − S, |N (v) ∩ S| ≥ k, where N (v) is the set of all neighbors of v. The size of a smallest k-dominating set is called the k-domination number of G and is denoted by γk (G). Also, for the graph G, and a real number 0 < α ≤ 1, a set S ⊆ V is an α-dominating set in G if for each v ∈ V − S, |N (v) ∩ S| ≥ αd(v), where d(v) is the degree of vertex v. The minimum size of an α-dominating set in G is called α-domination number of G and is denoted by γα (G). In recent years, the domination in graphs has found numerous applications. The kdomination number and α-domination number of a graph were introduced by Fink and Jacobson [4,5] and Dunbar et al. [3]. For a survey on the area of domination in graphs and its applications, we refer the reader to [6,7]. The generalized Petersen graph P(n, k) = (V, E) is defined as follows: V = {v1 , v2 , . . . , vn , u 1 , u 2 , . . . , u n }, © Indian Academy of Sciences

17

Page 2 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

Table 1. Cheng’s results on the 2-domination number of generalized Petersen graphs. Graph

2-Domination number

P(n, 1) P(5k, 5t + 2) P(5k, 5t + 3) P(5k + 3, 2) P(5k + 4, 2) P(6, 2) P(7, 2)

E=

n 

n 4k, k > 0 and 0 ≤ t < k 4k, k > 0 and 0 ≤ t < k 4k + 3, k > 0 4k + 4, k > 0 6 7

{(vi , u i ), (vi , vi+1 ), (u i , u i+k )},

i=1

where the subscripts are taken modulo n. For k = 1, the problem of finding the k-domination number of generalized Petersen graphs has been considered by some researchers [1,8–10]. Recently, the 2-domination number of generalized Petersen graphs was considered by Cheng [2]. We summarize Cheng’s results on the 2-domination number of generalized Petersen graphs in table 1. Furthermore, she presented the following conjectures: Conjecture 1. If

1 3

< α ≤ 23 , then γα (P(5k + 1, 2)) = 4k + 2, for k > 0.

Conjecture 2. If

1 3

< α ≤ 23 , then γα (P(5k + 2, 2)) = 4k + 3, for k > 0.

Since P(n, 2) for n ≥ 3 and n = 4 is a 3-regular graph, clearly for 13 < α ≤ 23 , γα (P(n, 2)) = γ2 (P(n, 2)). In this paper, we prove the above two conjectures. Furthermore, we determine the exact value of 2-domination of generalized Petersen graphs P(5k + 4, 3) and P(2k, k), for k > 0. Finally, we give lower and upper bounds on the 2-domination number of P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3) for k > 0. It is clear that the 2-domination number of generalized Petersen graph P(5k, 3) can be easily obtained as in the third row of table 1. In section 2, we determine the value of the 2-domination number of generalized Petersen graphs P(2k, k) and P(5k + 4, 3). In section 3, we prove Conjectures 1 and 2. In section 4, we give lower and upper bounds on the 2-domination number of graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3), for k > 0. Furthermore, we present our conjectures on the exact 2-domination number of graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3), for k > 0. Finally, we conclude the paper in section 5. 2. 2-Domination number of P(2k, k) and P(5k + 4, 3) In this section, we determine the 2-domination number of P(2k, k) and P(5k +4, 3). First, we consider the graph P(2k, k).

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

Page 3 of 12

17

vi+k

ui+k ui vi

Figure 1. An induced subgraph Hi .

Theorem 1. For k ≥ 2, γ2 (P(2k, k)) = 2k.

(1)

Proof. First, we prove that γ2 (P(2k, k)) ≤ 2k. ⎧ k k ⎨ i=1 {v2i−1 } ∪ i=1 {u 2i } k Let S =  k2 ⎩ i=1 {v2i−1 , u 2i } ∪ {v , u 2i−1 } i= k +1 2i

if k is odd, if k is even.

2

Clearly, |S| = 2k. It is not hard to prove that S is a 2-dominating set in P(2k, k). Now, we prove that γ2 (P(2k, k)) ≥ 2k. Let D be a 2-dominating set in P(2k, k) with minimum cardinality γ2 (P(2k, k)). For each integer 1 ≤ i ≤ n, let Hi be the induced subgraph of P(2k, k) with vertex set Vi , where Vi = {vi , u i , u i+k , vi+k } (see figure 1). Suppose that Di = Vi ∩ D. Since the degree of both u i and u i+k in P(2k, k) are two, so (i) u i ∈ D or vi , u i+k ∈ D and (ii) u i+k ∈ D or u i , vi+k ∈ D. It follows |Di | = |D ∩ {vi , u i , u i+k , vi+k }| ≥ 2 for every i. On the other hand, for each vertex v of P(2k, k), there are exactly two sets Vi such that v belongs to them. So, 2|D| =

n 

|Di | ≥ 2n.

i=1

Hence γ2 (P(2k, k)) = |D| ≥ n.  Now, we consider the generalized Petersen graph P(5k + 4, 3). Before we determine the 2-domination number of graph P(5k + 4, 3), we present the following lemma on the α-domination number of a regular graph due to Dunbar et al. [3]

17

Page 4 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

Lemma 1 [3]. If G is a k-regular graph with n vertices and i is an integer with 1 ≤ i ≤ k, then  i ×n . (2) γi/k (G) ≥ i +k Theorem 2. For each k > 0, γ2 (P(5k + 4, 3)) = 4k + 4.

(3)

Proof. First, we show that γ2 (P(5k + 4, 3)) ≥ 4k + 4. By Lemma 1, we have γ2/3 (P(5k + 4, 3)) ≥ 4k + 4. Since γα (P(5k + 4, 3)) = γ2 (P(5k + 4, 3)) for α = 23 , the lower bound holds. Now, we show that γ2 (P(5k + 4, 3)) ≤ 4k + 4. Let S = {vi , u j |i ≡ 1, 4 (mod 5), j ≡ 2, 3 (mod 5)}. It is easy to see |S| = 4k +4. Also V − S = {vi , u j |i ≡ 0, 2, 3 (mod 5), j ≡ 0, 1, 4 (mod 5)}. Let x ∈ V − S. If x = vi and i ≡ 0(mod 5), then vi−1 , vi+1 ∈ N (vi ) ∩ S. If x = vi and i ≡ 2(mod 5), then u i , vi−1 ∈ N (vi ) ∩ S. If x = vi and i ≡ 3(mod 5), then u i , vi+1 ∈ N (vi ) ∩ S. If x = u j and j ≡ 0(mod 5), then u j−3 , u j+3 ∈ N (u j ) ∩ S. If x = u j and j ≡ 1(mod 5), then v j , u j−3 ∈ N (u j ) ∩ S. If x = u j and j ≡ 4(mod 5), then v j , u j+3 ∈ N (u j ) ∩ S. Hence, S is a 2-dominating set in P(5k + 4, 3), and this proves the theorem.  3. The 2-domination number of P(5k + 1, 2) and P(5k + 2, 2) In this section, we prove the conjectures of Cheng [2]. At first, we have some definitions that we need later. Here, we denote P(5k +1, 2) or P(5k +2, 2) by G(n) where n = 5k +1 or n = 5k + 2. Consider a set D ⊆ V that is a 2-dominating set in G(n). We define three types of blocks in G based on D. DEFINITION 1 (a) We call B 1 a block of type I with respect to D if it is an induced subgraph of G(n) on the vertex set {vi−1 , vi , vi+1 }, for some i with 1 ≤ i ≤ n, such that vi−1 , vi+1 ∈ D and / D (see figure 2(a)). In the figures we assume that the vertices with a circle surrounded vi ∈ are in D. (b) We call B 2 a block of type II with respect to D if it is an induced subgraph of G(n) on the vertex set {vi−1 , vi , vi+1 , vi+2 }, for some i with 1 ≤ i ≤ n, such that vi−1 , vi+2 ∈ D / D (see figure 2(b)). and vi , vi+1 ∈ (c) We call B 3 a block of type III with respect to D if it is an induced subgraph of G on the vertex set {vi , vi+1 }, for some 1 ≤ i ≤ n, such that vi , vi+1 ∈ D (see figure 2(c)). According to Definition 1 and since D is a 2-dominating set in G(n), we have the following observation. Observation 1. If B 2 is a block of type II with vertex set {vi−1 , vi , vi+1 , vi+2 }, then u i , u i+1 ∈ D.

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17 vi+1

vi vi+1

vi−1

(a)

Page 5 of 12 vi vi−1

vi+2

17 vi+1

vi

(b)

(c)

Figure 2. (a) Block of type I; (b) block of type II; (c) block of type III.

In the following, we prove some lemmas that are used in the proof of Theorem 3. Lemma 2. Suppose that C1 is the induced subgraph of G(n) on the vertex set {v1 , v2 , . . . , vn } (exterior cycle). Every 2-dominating set D of G(n) with minimum cardinality γ2 (G(n)) can be converted to a 2-dominating set D  of G(n) with |D  | = |D| such that cycle C1 contains at least one block of type II with respect to D  . Proof. If the cycle C1 contains at least one block of type II with respect to D, then trivially we choose D  := D. Now, suppose that the cycle C1 contains no blocks of type II with respect to D. We first assume that n is odd. Since n is odd, cycle C1 must contain at least one block of type III with respect to D because if C1 contains no blocks of type III, then C1 contains no three consecutive vertices vi−1 , vi and vi+1 , and therefore vi is dominated by at most one vertex of C1 , i.e., a contradiction to D is a 2-dominating set of G(n). Without loss of generality, we assume that B 3 is a block of type III with vertex set {vi−1 , vi } on the cycle C1 with respect to D. We consider three cases. • Case 1. The block B 3 has two adjacent blocks of type I, denoted by B11 and B21 with vertex sets {vi , vi+1 , vi+2 } and {vi−3 , vi−2 , vi−1 }, respectively (see figure 3(a)) If u i ∈ D, then we choose D  := (D − {vi }) ∪ {u i+1 }. Otherwise, we have u i−2 ∈ D, and therefore we choose D  := (D − {vi−1 }) ∪ {u i−1 }. In each of the two cases, it is clear that D  is a 2-dominating set in G(n), |D  | = |D| and C1 has a block of type II with respect to D  . • Case 2. The block B 3 has two adjacent blocks, denoted by B11 and B13 of types I and III respectively, with vertex sets {vi−3 , vi−2 , vi−1 } and {vi , vi+1 } (see figure 3(b)). / D, then u i−2 ∈ D. So, we choose D  := (D − {vi−1 }) ∪ {u i−1 }. The case If u i ∈ u i ∈ D cannot occur because if u i ∈ D, then D − {vi } is a 2-dominating set in G(n) which contradicts minimality of D. It is clear that D  is a 2-dominating set, |D  | = |D| and C1 has a block of type II with respect to D  . By symmetric arguments, the proof is same for the case that the block B 3 has two adjacent blocks, denoted by B11 and B13 of types I and III, receptively with vertex set {vi , vi+1 , vi+2 } and {vi−1 , vi−2 }. • Case 3. The block B 3 has two adjacent blocks of type III, denoted by B13 and B23 with vertex sets {vi , vi+1 } and {vi−1 , vi−2 }, respectively (see figure 3(c)). / D and u i ∈ / D because otherwise we can easily find a In this case we have u i−1 ∈ 2-dominating set with size smaller than |D|, i.e., a contradiction to minimality of D. Now, we choose D  = (D − {vi , vi−1 }) ∪ {u i , u i−1 }. It is clear that D  is a 2-dominating set in G(n), |D  | = |D| and C1 has a block of type II with respect to D  . Now, assume that n is even. If cycle C1 contains at least one block of type III with respect to D, then D  is characterized by the above three cases in analogy with the case n is odd. So, we assume that cycle C1 contains no blocks of type III with respect to D. We

17

Page 6 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17 vi+2

vi+1

ui+2

ui+1

vi ui

vi−1 ui−1

vi−2

vi−3

ui−2

ui−3

(a) vi+1

vi

vi−1

vi−2

vi−3

vi+1

vi

vi−1

vi−2

ui+1

ui

ui−1

ui−2

ui−3

ui+1

ui

ui−1

ui−2

(b)

(c)

Figure 3. Case n is odd in Lemma 2. (a) Case 1, (b) Case 2 and (c) Case 3.

assume that B11 is an arbitrary block of type I with respect to D on C1 . Without loss of generality, assume that the vertex set of B11 is {v5 , v6 , v7 } (see figure 4(a)). • Case 1. u 6 ∈ D and u 7 ∈ / D. Since u 7 ∈ / D, we have u 5 ∈ D or u 9 ∈ D. First, we / D and u 9 ∈ D. If u 8 ∈ / D, then we have u 10 ∈ D and therefore we suppose that u 5 ∈ choose D  := (D − {v9 }) ∪ {v8 }. If u 8 ∈ D, we choose D  := (D − {v9 }) ∪ {v10 }. In / D, we choose D  = (D − {v5 }) ∪ {v4 }. The case u 5 ∈ D the case u 5 ∈ D and u 9 ∈ and u 9 ∈ D cannot occur because if u 5 ∈ D and u 9 ∈ D, and if u 8 ∈ D, we choose / D, then u 10 ∈ D, hence we D  = (D − {v5 , u 6 , v7 , u 8 , v9 }) ∪ {u 4 , v6 , v8 , u 10 } and if u 8 ∈ choose D  = (D − {v5 , u 6 , v7 , v9 }) ∪ {u 4 , v6 , v8 }. In both the cases, D  is a 2-dominating set and |D  | < |D|, i.e., a contradiction to minimality of D. • Case 2. u 6 ∈ D and u 7 ∈ D. Hence, we choose D  = (D − {v7 }) ∪ {v8 }. / D. Then u 4 , u 8 ∈ D. Now, if u 7 ∈ D, we choose D  := (D − {v7 }) ∪ {v6 }. • Case 3. u 6 ∈ / D, then we have u 5 ∈ D or u 9 ∈ D. In the case u 5 ∈ D and u 9 ∈ / D, we If u 7 ∈ / D and u 9 ∈ D, we choose choose D  := (D − {v5 }) ∪ {v6 } and in the case u 5 ∈ D  := (D − {v9 }) ∪ {v10 }. The case u 5 , u 9 ∈ D cannot occur because if u 5 , u 9 ∈ D, then set D  := (D − {v5 , v7 , u 8 , v9 }) ∪ {v6 , v8 , u 10 } is a 2-dominating set in G(n) with size smaller than |D|, i.e., a contradiction. It is easy to verify that the set D  which is constructed in the above argument is a 2dominating set in G(n) with |D  | = |D| and the cycle C1 has at least one block of type II  with respect to D  . Let V j := {v j , v j+1 , v j+2 , v j+3 , v j+4 , u j , u j+1 , u j+2 , u j+3 , u j+4 } and let G j be the induced subgraph of G(n) with the vertex set V j . Furthermore, let D be a 2-dominating set in G(n) with the minimum cardinality γ2 (G(n)). By Lemma 2, we may assume that the cycle C1 contains at least one block of type II with respect to D with vertex set / D. Moreover, let F1 := (D − V5 ) ∪ {v1 , v2 , v3 , v4 } in which v1 , v4 ∈ D and v2 , v3 ∈ {v6 , u 7 , u 8 , v9 } and F2 := F1 ∪ {u 11 }. Let G 5 be the subgraph of G induced by V5 (see figure 4(b)). Now, with these assumptions, we prove the following results. Lemma 3. Each 2-dominating set D of G(n) with minimum cardinality contains at least 3 and at most 5 elements of V5 . Proof. Obviously, |D ∩ {v5 , v6 , v7 , v8 , v9 }| and |D ∩ {u 5 , u 6 , u 7 , u 8 , u 9 }| are at least one. Hence, |D ∩ V5 | ≥ 2. We claim that |D ∩ V5 | = 2. If |D ∩ V5 | = 2, then we necessarily

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17 v3 v4 v5 v6 v7 v8 v9 v10 v11 u3 u4 u5 u6 u7 u8 u9 u10 u11

Page 7 of 12

17

v11 v10 v9 v8 v7 v6 v5 v4 v3 v2 v1 u11 u10 u9 u8 u7 u6 u5 u4 u3 u2 u1

(a)

(b)

Figure 4. (a) The block B11 . (b) The induced subgraph G 5 .

have v7 ∈ D and v5 , v6 , v8 , v9 ∈ / D. Since v6 , v5 ∈ / D, u 6 ∈ D, and since v8 , v9 ∈ / D, u 8 ∈ D. Hence, {v7 , u 6 , u 8 } ⊆ D, which contradicts |D ∩ V5 | = 2. Thus, |D ∩ V5 | = 2 and therefore |D ∩ V5 | ≥ 3. If D contains more than 5 elements of V5 , then it is easy to see that F2 , as defined above, is a 2-dominating set of G(n), which contradicts the assumption that D is a minimum 2-dominating set of G(n). Lemma 4. There exists a 2-dominating set S  in G(n) (n = 5k + 1 or n = 5k + 2) with |S  | = |D| such that for every integer j which is a multiple of 5 and j < 5k, V j ∩ S  = {v j+1 , u j+2 , u j+3 , v j+4 }, where the subscripts are taken modulo n. Proof. First, we construct a 2-dominating set in G(n) denoted by S5 such that V5 ∩ S5 = {v6 , u 7 , u 8 , v9 } and |S5 | = |D|. Later, we use S5 to construct S  . By Lemma 3, we have 3 ≤ |D ∩ V5 | ≤ 5. In the following, consider figure 4(b). First, suppose that |D ∩ V5 | = 5. In this case, we take S5 = F2 . It is easy to verify that in this case the set S5 is a 2-dominating set of G(n). Now, suppose that |D ∩ V5 | = 3. It is not hard to see that in this case, we necessarily must have D ∩ V5 = {v6 , u 7 , v8 }. Hence, since D is a 2-dominating set of G(n) and by our assumption that C1 contains at least a block of type II with respect to D with vertex set {v1 , v2 , v3 , v4 }, we must have {u 4 , v10 , u 10 , u 11 } ⊆ D. Note that in this case if u 12 ∈ D, then the set (D − {u 4 , u 10 , v8 }) ∪ {u 8 , v9 } is a 2-dominating set of G(n) with / D. Now, we take size smaller than |D| which is a contradiction. Hence, we have u 12 ∈ S5 := (D − {u 4 , u 10 , v8 }) ∪ {u 8 , v9 , u 12 }. Clearly, S5 is a 2-dominating set of G(n) with |S5 | = |D| and V5 ∩ S5 = {v6 , u 7 , u 8 , v9 }. / D, we take S5 = F1 . It is easy to verify Now, suppose that |D ∩ V5 | = 4. If u 9 ∈ that in this case the set S5 is a 2-dominating set of G(n). If u 9 ∈ D, then we consider the following cases: • Case a. v9 ∈ / D. It is clear that |D ∩ {v5 , v6 , v7 }| ≥ 1. Subcase i. v8 ∈ D. Subsubcase 1. |D ∩ {v5 , v6 , v7 }| = 1. If D ∩ {v5 , v6 , v7 } = {v6 }, then u 5 ∈ D or u 7 ∈ D. If both vertices u 5 and u 7 belong to D, then we choose S5 := F2 . / D. If u 6 ∈ D, then we choose S5 := F2 . If u 6 ∈ / D, Now suppose that u 5 ∈ D and u 7 ∈ then u 4 ∈ D or u 8 ∈ D. Both vertices u 4 and u 8 cannot belong to D because otherwise F2 −{u 4 } is a 2-dominating set in G(n) with size smaller than |D| which is a contradiction. / D) or (u 4 ∈ / D and u 8 ∈ D), then we choose S5 := F2 − {u 4 } or So, if (u 4 ∈ D and u 8 ∈ / D and u 7 ∈ D. S5 := F2 . With the same argument, we can construct S5 for the case u 5 ∈ Now, suppose that D ∩ {v5 , v6 , v7 } = {v5 } or D ∩ {v5 , v6 , v7 } = {v7 }. If D ∩ {v5 , v6 , v7 } = {v5 }, then u 6 , u 7 ∈ D, and if D ∩ {v5 , v6 , v7 } = {v7 }, then u 5 , u 6 ∈ D.

17

Page 8 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

Clearly, in both cases we choose S5 := F2 . It is notable that in the above cases, u 11 ∈ / D because otherwise we can easily construct a 2-dominating set with size smaller than |D| which is a contradiction. Subsubcase 2. |D ∩ {v5 , v6 , v7 }| = 2. If D ∩ {v5 , v6 , v7 } = {v5 , v6 }, then it is clear that |D ∩ {u 5 , u 6 , u 7 }| ≥ 1, so we choose S5 := F2 . Now suppose that D ∩ {v5 , v6 , v7 } = / D cannot occur because {v5 , v7 }. If u 6 ∈ D, then we choose S5 := F2 . The case u 6 ∈ otherwise we must have u 4 , u 8 ∈ D, hence F2 −{u 4 } is a 2-dominating set in G(n) with size smaller than |D| which is a contradiction. Now, suppose that D ∩ {v5 , v6 , v7 } = {v6 , v7 }. Clearly |D ∩ {u 5 , u 6 , u 7 }| ≥ 1, so we choose S5 := F2 . It is notable that in the above / D because otherwise we can easily construct a 2-dominating set with size cases, u 11 ∈ smaller than |D| which is a contradiction. Subsubcase 3. |D ∩ {v5 , v6 , v7 }| = 3. This case cannot occur because otherwise we have u 4 ∈ D or u 6 ∈ D or u 8 ∈ D, so using F2 we can easily construct a 2-dominating set in G(n) with size smaller than |D| which is a contradiction. Subcase ii. v8 ∈ / D. Since v9 ∈ / D, v7 , u 8 ∈ D. Now if D ∩ {v5 , v6 } = ∅, then u 5 , u 6 ∈ D, so we choose S5 := F2 . Now suppose that D ∩ {v5 , v6 } = ∅. First, we assume that D∩{v5 , v6 } = {v5 }. If D∩{u 5 , u 6 } = ∅, then we choose S5 := F2 , and if D∩{u 5 , u 6 } = ∅, then u 4 ∈ D, so we choose S5 := F2 − {u 4 }. Now assume that D ∩ {v5 , v6 } = {v6 }. If D ∩ {u 5 , u 6 } = ∅, then we must have u 7 ∈ D, so we choose S5 := F2 . Similarly, in the case D ∩ {u 5 , u 6 } = ∅, we consider S5 := F2 . • Case b. v9 ∈ D. We can easily verify that in this case, we have |D ∩ {v5 , v6 , v7 , v8 , u 5 , u 6 , u 7 , u 8 }| ≥ 3. Hence, we choose S5 := F2 . It is notable that in this case, we have / D, because otherwise F1 is a 2-dominating set in G(n) with size smaller than |D| u 11 ∈ which is a contradiction. Now, we are ready to construct the set S  . The following algorithm, Algorithm 1, generates the set S  : Algorithm 1: Constructing the set S  . 1 2 3 4 5 6 7 8 9 10

S  := S5 ; if n = 5K + 1 then i n := n − 6; if n = 5k + 2 then i n := n − 7; j := 10; while j ≤ i n do S  := (S  − S  ∩ V j ) ∪ {v j+1 , u j+2 , u j+3 , v j+4 }; j = j + 5; return S  ;

The argument for correctness of Algorithm 1 is easy by considering the way of constructing S5 . Clearly, the set S  generated by Algorithm 1 is a 2-dominating set in G(n) with |S  | = |D| such that for every integer j which is a multiple of 5 and j < 5k, V j ∩ S  = {v j+1 , u j+2 , u j+3 , v j+4 } (see figure 5). 

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

vj+4 uj+4

vj+3

uj+3

vj+2 uj+2

Page 9 of 12

vj+1

vj

uj+1

uj

17

Figure 5. The induced subgraph G j satisfies the condition V j ∩ S  {v j+1 , u j+2 , u j+3 , v j+4 }

=

Lemma 5. Suppose that n = 5k +1 and H is the induced subgraph of G(n) on the vertices V (H ) := {vn , vn−1 , u n , u n−1 }. Also, assume that S  is the set which is constructed in Lemma 4. There exists a 2-dominating set S in G(n) with |S| = |S  | such that |S ∩ V (H )| ≥ 2. Moreover, for every integer j which is a multiple of 5 and j < 5k, V j ∩ S = {v j+1 , u j+2 , u j+3 , v j+4 }. Proof. If |S  ∩ V (H )| ≥ 2, take S = S  . If |S  ∩ V (H )| = 1, then S  ∩ V (H ) = {vn } or {vn−1 }. If S  ∩ V (H ) = {vn }, take S = (S  − {u 1 }) ∪ {u n−1 } and if S  ∩ V (H ) = {vn−1 }, take S = (S  − {u n−2 }) ∪ {u n }. Clearly the set S constructed in the above argument satisfies the conditions of Lemma 5.  Lemma 6. Suppose that n = 5k + 2 and H is the induced subgraph of G(n) on the vertices V (H ) := {vn , vn−1 , vn−2 , u n , u n−1 , u n−2 }. Also, assume that S  is the set which is constructed in Lemma 4. There exists a 2-dominating set S of G(n) with |S| = |S  | such that |S ∩ V (H )| ≥ 3. Moreover, for every integer j which is a multiple of 5 and j < 5k, V j ∩ S = {v j+1 , u j+2 , u j+3 , v j+4 }. Proof. If |S  ∩ {vn , vn−1 , vn−2 }| = 2 or 3, take S = S  . If S  ∩ {vn , vn−1 , vn−2 } = {vn } or {vn−2 }, take S = S  . For the case S  ∩ {vn , vn−1 , vn−2 } = {vn−1 } and u n−1 ∈ S  , / S  , take take S = S  . For the case S  ∩ {vn , vn−1 , vn−2 } = {vn−1 } and u n−1 ∈  S := (S − {u 1 }) ∪ {u n−1 }. It is easy to see that the set S constructed in the above argument satisfies the conditions of Lemma 6.  The following theorem proves Conjectures 1 and 2. Theorem 3. For each k > 0, we have γ2 (P(5k + 1, 2)) = 4k + 2, γ2 (P(5k + 2, 2)) = 4k + 3. Proof. In [2], Cheng proved that γ2 (P(5k +1, 2)) ≤ 4k +2 and γ2 (P(5k +2, 2)) ≤ 4k +3. Also, she proved that γ2 (P(6, 2)) = 6 and γ2 (P(7, 2)) = 7. Thus, we need to prove lower bounds for n ≥ 11. Suppose that D is a 2-dominating set in G(n) with minimum cardinality γ2 (G(n)). Using Lemma 2, we construct a 2-dominating set D  in G(n) with |D  | = |D| such that the cycle

17

Page 10 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

C1 contains at least one block of type II with respect to D  . Without loss of generality, we may assume that C1 contains the block of type II with vertex set {v1 , v2 , v3 , v4 } such that / D  . Then, using Lemma 4 and set D  , we construct a dominating v1 , v4 ∈ D  and v2 , v3 ∈   set S of G(n) with |S | = |D  | such that all induced subgraphs denoted by G j of G(n) with the vertex set V j := {v j , v j+1 , v j+2 , v j+3 , v j+4 , u j , u j+1 , u j+2 , u j+3 , u j+4 } where j is a multiple of 5 satisfy the condition V j ∩ S  = {v j+1 , u j+2 , u j+3 , v j+4 }. Finally, using Lemmas 5 and 6, and set S  , we construct a 2-dominating set S in G(n) with |S| = |S  | such that |S ∩ V (H )| ≥ 2 when n = 5k + 1 and |S ∩ V (H )| ≥ 3 when n = 5k + 2 (H was defined in Lemmas 5 and 6). Obviously all induced subgraphs G j of G(n) satisfy the condition V j ∩ S = {v j+1 , u j+2 , u j+3 , v j+4 }. Now, according to the construction of set S, we have • If n = 5k + 1, then 



5k − 5 n−6 +4+2=4 + 6 = 4(k − 1) + 6 = 4k + 2. |S| ≥ 4 5 5 • If n = 5k + 2, then



 n−7 5k − 5 |S| ≥ 4 +4+3=4 + 7 = 4(k − 1) + 7 = 4k + 3. 5 5 This completes the proof.  4. 2-Domination number of graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3) In this section, we give a good lower and upper bounds on the 2-domination number of graphs P(5k +1, 3), P(5k +2, 3) and P(5k +3, 3). Finally, we will present our conjecture on the exact 2-domination number of graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3). Theorem 4. For each k > 0, 4k + 1 ≤ γ2 (P(5k + 1, 3)) ≤ 4k + 2, 4k + 2 ≤ γ2 (P(5k + 2, 3)) ≤ 4k + 3, 4k + 3 ≤ γ2 (P(5k + 3, 3)) ≤ 4k + 4. Proof. Using Lemma 1, the lower bounds are easily obtained. Now, we prove the upper bounds. We define the sets S5k+1 , S5k+2 and S5k+3 as follows: S5k+1 := {vi , u j |i ≡ 1, 4(mod 5), j ≡ 2, 3(mod 5)} ∪ {u n−2 }, S5k+2 := {vi , u j |i ≡ 1, 4(mod 5), j ≡ 2, 3(mod 5) and 1 ≤ j ≤ 5k − 2} ∪ {u n−2 , u n−3 }, S5k+3 := {vi , u j |i ≡ 1, 4(mod 5), j ≡ 2, 3(mod 5)} ∪ {u n−2 }. It is easy to see that |S5k+1 | = 4k+2, |S5k+2 | = 4k+3 and |S5k+3 | = 4k+4. Now, we prove that S5k+1 , S5k+2 and S5k+3 are 2-dominating sets in graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3), respectively. First, we consider S5k+1 . It is clear that V − S5k+1 = {vi , u j |i ≡ 0, 2, 3(mod 5), j ≡ 0, 1, 4(mod 5)} − {u n−2 }.

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

Page 11 of 12

17

Suppose that x = vi is an arbitrary element of V − S5k+1 . We know the three neighbors of vi are vi−1 , vi+1 and u i . Now suppose that i ≡ 0(mod 5). Since i is dividable by 5, i − 1 ≡ 4(mod 5) and i + 1 ≡ 1(mod 5). Hence, vi−1 , vi+1 ∈ S5k+1 . Now assume that i ≡ 2(mod 5). Clearly u i ∈ S5k+1 and also since i − 1 ≡ 1(mod 5), vi−1 ∈ S5k+1 . Now suppose that i ≡ 3(mod 5). It is clear that u i ∈ S5k+1 and since i + 1 ≡ 4(mod 5), vi+1 ∈ S5k+1 . Now assume that x = u j . The three neighbors of u j are u j−3 , u j+3 and v j . If j ≡ 0(mod 5), then j − 3 ≡ 2(mod 5) and j + 3 ≡ 3(mod 5). Hence, u j−3 , u j+3 ∈ S5k+1 . Now suppose that j ≡ 1(mod 5). Clearly v j ∈ S5k+1 . In this case, if j = 1, since j − 3 ≡ 3(mod 5), u j−3 ∈ S5k+1 , and if j = 1, we have u n−2 ∈ S5k+1 . If j ≡ 4(mod 5), then v j ∈ S5k+1 and since j + 3 ≡ 2(mod 5), u j+3 ∈ S5k+1 . So, it is clear that each vertex in V − S5k+1 is dominated by at least two vertices in S5k+1 . To prove that the set S5k+3 is a 2-dominating set, we use an argument similar to the proof for the set S5k+1 . Now, we consider the set S5k+2 . Clearly, we have V − S5k+2 = {u n } ∪ {vi , u j |i ≡ 0, 2, 3(mod 5), j ≡ 0, 1, 4(mod 5)} −{u n−2 , u n−3 }. Let x = vi be an arbitrary element of V − S5k+2 . The three neighbors of vi are vi−1 , vi+1 and u i . Now suppose that i ≡ 0(mod 5). Since i is dividable by 5, we have i −1 ≡ 4(mod 5) and i + 1 ≡ 1(mod 5). Thus vi−1 , vi+1 ∈ S5k+2 . Now assume that i ≡ 2(mod 5). If i = n, then clearly u i ∈ S5k+2 and also since i − 1 ≡ 1(mod 5), vi−1 ∈ S5k+2 , and if i = n, then it is obvious that u 1 , u n−1 ∈ S5k+2 . Now suppose that i ≡ 3(mod 5). It is clear that u i ∈ S5k+2 and i + 1 ≡ 4(mod 5). Hence, vi+1 ∈ S5k+2 . Now suppose that x = u j . The three neighbors of u j are u j−3 , u j+3 and v j . If j ≡ 0(mod 5), then j − 3 ≡ 2(mod 5) and j + 3 ≡ 3(mod 5). Hence, u j−3 , u j+3 ∈ S5k+2 . Now suppose that j ≡ 1(mod 5). It is clear that v j ∈ S5k+2 . In this case, if j = 1, since j − 3 ≡ 3(mod 5), we have u j−3 ∈ S5k+2 , otherwise we have u n−2 ∈ S5k+2 . If j ≡ 4(mod 5), then v j ∈ S5k+2 and since j + 3 ≡ 2(mod 5), we have u j+3 ∈ S5k+2 . Finally, suppose that x = u n . Clearly u 3 , u n−3 ∈ S5k+2 . It is easy to see that each vertex in V − S5k+2 is dominated by at least two vertices in S5k+2 . Hence, we conclude that the sets S5k+1 , S5k+2 and S5k+3 are 2-dominating sets in P(5k+ 1, 3), P(5k + 2, 3) and P(5k + 3, 3), respectively.  Finally, we propose the following conjecture. Conjecture 3. For each k > 0, γ2 (P(5k + 1, 3)) = 4k + 2, γ2 (P(5k + 2, 3)) = 4k + 3, γ2 (P(5k + 3, 3)) = 4k + 4.

17

Page 12 of 12

Proc. Indian Acad. Sci. (Math. Sci.) (2018) 128:17

5. Conclusion In this paper, we determined the 2-domination number of generalized Petersen graphs P(2k, k) and P(5k + 4, 3). Furthermore, we proved that the 2-domination number of generalized Petersen graphs P(5k + 1, 2) and P(5k + 2, 2) are 4k + 2 and 4k + 3, respectively. Moreover, we presented good lower and upper bounds on the 2-domination number of graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3). Finally, we presented a conjecture on the 2-domination number of P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3). The future work involves finding the 2-domination number of generalized Petersen graphs P(n, k) for k > 3.

Acknowledgements The authors would like to thank the reviewers for their comments to improve the paper and clarify some of the proofs.

References [1] Behzad A, Behzad M and Praeger C E, On the domination number of the generalized Petersen graphs, Discrete Math. 308 (2008) 603–610 [2] Cheng Y, α-domination of generalized Petersen graph, PhD Thesis (2013) (National Chiao Tung University) [3] Dunbar J E, Hoffman D G, Laskar R C and Markus L R, α-domination, Discrete Math. 211 (2000) 11–26 [4] Fink J F and Jacobson M S, n-Domination in graphs, in Graph Theory with Applications to Algorithms and Computer Science, edited by Y Alavi and A J Schwenk (1985a) (London: Wiley) pp. 283–300 [5] Fink J F and Jacobson M S, On n-domination, n-dependence and forbidden subgraphs, in Graph Theory with Applications to Algorithms and Computer Science, edited by Y Alavi and A J Schwenk (1985b) (London: Wiley) pp. 301–311 [6] Haynes T W, Hedetniemi S T and Slater P J, Fundamentals of Domination in Graphs (1998a) (New York: Marcel Dekker Inc.) [7] Haynes T W, Hedetniemi S T and Slater P J, Domination in Graphs: Advanced Topics (1998b) (New York: Marcel Dekker Inc.) [8] Javad Ebrahimi B, Jahanbakht N and Mahmoodian E S, Vertex domination of generalized Petersen graphs, Discrete Math. 309 (2009) 4355–4361 [9] Wang H, Xu X, Yang Y and Wang G, On the domination number of generalized Petersen graphs p(ck, k), arXiv preprint arXiv:1103.2427 (2011) [10] Yan H, Kang L and Xu G, The exact domination number of the generalized Petersen graphs, Discrete Math. 309 (2009) 2596–2607

Communicating Editor: Sharad S Sane