2-Domination number of generalized Petersen graphs

Let (G=(V,E)) be a graph. A subset (Ssubseteq 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).)