On the [1,2]-domination number of generalized Petersen graphs

摘要

A dominating set in a graph G=(V,E) is a subset S of V such that N[S]=V, that is, each vertex of G either belongs to S or is adjacent to at least one vertex in S. The minimum cardinality of a dominating set in G is called the domination number, denoted by γ(G). A subset S of V is a [1,2]-set if, for every vertex v ∈ V∖S, v is adjacent to at least one but no more than two vertices in S. The [1,2]-domination number of a graph G, denoted by γ[1, 2](G), is the minimum cardinality of a [1, 2]-set of Chellali et al. gave some bounds for γ[1, 2](G) and proposed the following problem: which graphs satisfy γ(G)=γ[1,2](G). Ebrahimi et al. determined the exact value of the domination number for generalized Petersen graphs P(n, k) when k ∈ {1, 2, 3}. In this paper, we determine the exact values of γ[1, 2](P(n, k)) for k ∈ {1, 2, 3}. We also show that γ[1,2](P(n,k))=γ(P(n,k)) for k=1 and k=3, respectively, while for k=2, γ[1, 2](P(n, k)) ≠ γ(P(n, k)) except for n=6,7,9,12.