Domination in the generalized Petersen graph P(ck, k)

Abstract

Let G = (V, E) be a graph. A subset S C V is a dominating set of G, if every vertex u € V - S is dominated by some vertex v € S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. Determining the domination number of a graph G is an NP-complete problem, and only for few families of graphs, the exact domination number is known. In this paper, we study the domination number for the generalized Petersen graph P(ck,k), where c ≥ 3 is a constant. We obtain upper bound on γ(P(ck, k)) for general c. We also show that γ(P(3k, k)) = [5k/3] for any k ≥ 1, and γ(P(4k, k)) = 2k for odd k.