[1,2]-Domination in Generalized Petersen Graphs
Fairouz Beggas Volker Turau Mohammed Haddad Hamamache Kheddouci





F. Beggas, V. Turau, M. Haddad and H. Kheddouci
[1,2]-Domination in Generalized Petersen Graphs












^aUniversity of Claude Bernard Lyon 1, 43 Bd du 11 Novembre 1918, F-69622, Villeurbanne, France
 ^bInstitute of Telematics, Hamburg University of Technology, 21073 Hamburg, Germany, Am Schwarzenberg-Campus 3


[1,2]-DOMINATION IN GENERALIZED PETERSEN GRAPHS[This work is supported by PHC PROCOPE 2015-2017, project id 33394TD and PPP PROCOPE 2015, project id 57134870.]

    FIROUZ BEGGAS^a, VOLKER TURAU^b, MOHAMMED HADDAD^a[Contact author: mohammed.haddad@univ-lyon1.fr] 
 HAMAMACHE KHEDDOUCI^a
    December 30, 2023
================================================================================================================================================================











A vertex subset S of a graph G=(V,E) is a -dominating set
if each vertex of V\ S is adjacent to either one or two
vertices in S. The minimum cardinality of a -dominating set
of G, denoted by (G), is called the [1,2]-domination
number of G. In this paper the [1,2]-domination and the
[1,2]-total domination numbers of the generalized Petersen graphs
P(n,2) are determined.








§ INTRODUCTION

The study of domination problems in graph theory has a long history.
For an undirected graph G=(V,E) a subset S⊆ V is a dominating set if every vertex not in S has a neighbor in S.
The domination number (G) is the minimum size of a
dominating set in G. For many classes of graphs the exact values of
(G) are known, e.g., (P_n) =(C_n) =⌈ n/3⌉. Here
P_n and C_n are the paths and cycle graphs respectively with n
vertices. For the class of generalized Petersen graphs P(n,2)
introduced by Watkins <cit.> it was conjectured by Behzad
et al. that (P(n,2)) = ⌈ 3n/5 ⌉ holds
<cit.>. This conjecture was later independently verified
by several researchers <cit.>.

Over the years different variations of graph domination were
introduced, e.g., connected domination, independent domination, and
total domination. The domination number (G) and the total
domination number (G) of graph G are among the most well
studied parameters in graph theory. Some of these domination numbers
are known for generalized Petersen graphs. Cao et al. computed the
total domination number of P(n,2) as (P(n,2)) = 2⌈ n/3
⌉ <cit.>. Further results can be found in
<cit.>.

This paper considers
-domination, a concept introduced by Chellali et al.<cit.>. A subset S⊆ V is a -dominating set if every vertex not in S has at least one
and at most two neighbors in S, i.e., 1≤ |N(v)∩ S|≤ 2 for
all v∈ V ∖ S. The -domination number (G)
is the minimum size of a -dominating set in G. Obviously
(G) ≤(G) for any graph G. Chellali et al. proved that
if G is a P_4-free graph then (G) = (G). A
characterization of graphs with this property is an open problem. More
results about -domination can be found in <cit.>.
 
This paper also deals with the -total domination defined as follow.
A subset S⊆ V is a -total dominating set if every vertex v in V has at least one
and at most two neighbors in S, i.e., 1≤ |N(v)∩ S|≤ 2 for
all v∈ V. The -total domination number (G)
is the minimum size of a -total dominating set in G.
Clearly, (G) ≤(G) for each graph G.

In this paper we analyze the -domination numbers of the generalized
Petersen graphs P(n,2) and prove the following theorem.


   (P(n,2)) = {[       2n/3 n ≡ 0,3[6]; 2⌊ n/3 ⌋+1   n ≡ 1[6]; 2⌊ n/3 ⌋+2            ]. for n ≥ 5.   


Note that (P(n,2)) is by a factor of 10/9 larger than
(P(n,2)). After that, we investigate the problem of -total
domination and prove the following result.


(P(n,2)) = {[          5      n = 5;       2n/3 n ≡ 0,3[6]; 2⌊ n/3 ⌋+2            ]. for n ≥ 6.   


Note that (P(n,2))= (P(n,2)) except for the case n=5
and n ≡ 1[6]. Surprisingly (P(n,2)) is almost equal to
(P(n,2)).



§ NOTATION


This paper uses standard notation from graph theory which can be found
in textbooks on graph theory such as <cit.>. For an
extended study about domination concepts the reader is referred to
<cit.>.



  Let n, k∈ℕ with k < n/2. The generalized
    Petersen graph P(n,k) is the undirected graph with vertices
  {u_0,…,u_n-1} ∪ {v_0,…, v_n-1} and edges
  {(u_i,u_i+1),(u_i,v_i), (v_i,v_i+k) | 0≤ i < n}.


The
graphs P(n,k) are regular graphs with 2n vertices and Δ=3.
The domination number (P(n,k)) for some values of k are known
<cit.>. In particular Ebrahimi et al. proved
in <cit.> that (P(n,2)) = ⌈3n/5⌉.



In this paper indices are always interpreted modulo n, e.g.
v_n+i=v_i. Fig. 1 shows the graphs
P(5,2) and P(6,2), vertices depicted in black form a -dominating
set of minimum size, i.e., (P(5,2)) = (P(6,2)) = 4
and also for the graph P(5,2), vertices 
depicted in black form a -total dominating
set of minimum size (P(5,2))=5.

The proofs of this paper use the following notion of a block.


  A block b of P(n,2) is the subgraph induced by the six
  vertices {v_i-1,v_i,v_i+1,u_i-1,u_i,u_i+1} for any
  i∈{0,… n-1}. A block is called positive if two
  of the indices of {v_i-1,v_i,v_i+1} are odd, otherwise it
  is called negative.


Fig. <ref> shows a series of blocks of P(n,2). The
second block is positive while the other two are negative.
Note that blocks can overlap. If b is a block, the block to the
left is denoted by b^- and that to the right by b^+.








  Let S be a -dominating set. For a subset U⊆ V
  denote by γ_S(U) the number of vertices of S that are in
  U, i.e., γ_S(U)=|U ∩ S|. For i≥ 0 let B_i(S) be the set of all blocks b with γ_S(b)=i.


Note that B_0(S)= ∅ for any dominating set
S of P(n,2). Denote by f(n) the value of the right side of the
equation in Theorem <ref>. Note that f(n) = f(n-6) + 4 for
any n≥ 5.




§ DETERMINATION OF (P(N,2))


The correctness of Theorem <ref> for n < 12 can be
verified manually.
 
   (P(n,2)) = f(n) for 5≤ n <12. 
 











By inspection, we can easily see that
the following sets S_n are minimum -dominating sets of P(n,2).
S_5= { u_1,v_1,v_3,v_4 }, S_6= { u_1,v_1,u_4,v_4 },
S_7= { u_0,v_1,v_2,v_3,u_4 }, S_8= { u_1,v_1,u_4,v_4,v_6,v_7 }, 
S_9= { u_1,v_1,u_4,v_4,u_7,v_7 }, S_10= { u_1,v_1,u_4,v_4,u_7,v_7,u_8,v_8 } and
S_11= { u_1,v_1,u_4,v_4,u_7,v_7,v_9,v_10}.




  (P(n,2)) ≤ f(n) for n≥ 5.



  To prove that f(n) is an upper bound of (P(n,2)), we give
  in Fig. <ref> the corresponding construction for each
  case. For n ≡ 0,3[6], we choose the middle pair of nodes of
  each block. For the cases n ≡ 2,4,5[6], we do the same as the
  previous case by choosing the middle pair of nodes of each block.
  Then, we add two dominating nodes as depicted in red in
  Fig. <ref>. For the case n ≡ 1[6], we choose
  two nodes from each block as shown in Fig. <ref>
  except in the the two successive blocks preceding the block with
  only two nodes. In these two blocks we choose five nodes as depicted
  in Fig. <ref>. This means that we have 2n/3 nodes
  plus one additional dominating node.




Thus, it suffices to prove that f(n) is a lower bound. Assume that
there exists a minimal -dominating set S of P(n,2) with
|S|<f(n). Lemma <ref> yields n≥ 12. The remaining
proof is split into two parts depending on whether B_1(S) is
empty or not.



 §.§ Case B_1(S) = ∅


The vertices of P(n,2) are grouped into n pairs p_i={v_i,u_i} as
depicted in Fig. <ref>. Since B_1(S)= ∅
this means that for i=1,...,n
 
    γ_S(p_i) + γ_S(p_i+1) + γ_S(p_i+2) ≥
    2
  (subscripts are always taken modulo n). Note
that γ_S(p_i) ≤ 2 for all i. Consider the following system
of inequalities for integer valued variables x_0,…,x_n-1.
  
    [                 x_i                   ≤                   2; x_i + x_i+1 + x_i+2                   ≥                   2;       ∑_i=0^n-1 x_i                   <                f(n) ]
 



Note that x_i=γ_S(p_i) is a solution for these equations. We
will show that no solution of Eq. (<ref>) is induced by a
-dominating set. 


  Let x be a solution of Eq. (<ref>) with x_i=2 for some
  i. Let x̂=x except x̂_i+1=x̂_i+2=0 and
  x̂_i+3=2. Then x̂ is a solution of
  Eq. (<ref>) with ∑_i=0^n-1x̂_i ≤∑_i=0^n-1 x_i.


  Obviously x̂ satisfies the first two sets of inequalities.
  Note that x_i+1+x_i+2+x_i+3≥ 2 since x is a solution of
  Eq. (<ref>). Thus,
  x̂_i+1+x̂_i+2+x̂_i+3≤
  x_i+1+x_i+2+x_i+3.



  
  
  
  
  
  
  
  


  Let x be any  solution of Eq. (<ref>). Then
  x_i≤ 1 for i = 0,…, n-1.



  Let x be any solution of Eq. (<ref>) such that x_i=2 for
  some i. Without loss of generality i=0. By
  Lemma <ref> there exist a solution which coincides with
  x except x_1=x_2=0 and x_3=2. Repeatedly applying
  Lemma <ref> proves that there exits a solution x̂
  of Eq. (<ref>) with x̂_k=2 and
  x̂_k+1=x̂_k+2=0 for k=0,1,…, ⌊ n/3
  ⌋. If n ≡ 0 [3] then ∑_i=0^n-1x̂_i
  =2n/3 = f(n), which is impossible. Suppose n ≡ 1 [3]. Then
  x̂_n-1=2 otherwise the second constraint for i=n-2 would
  be violated. This leads to the contradiction ∑_i=0^n-1x̂_i =2⌊ n/3 ⌋ +2 ≥ f(n). Hence, n ≡
  2 [3]. Then x̂_n-2=2 otherwise the second constraint for
  i=n-2 is not satisfied. Again this leads to the contradiction
  ∑_i=0^n-1x̂_i =2⌊ n/3 ⌋ +2 = f(n). This
  proves x_i ≤ 1 for all i.



  If n ≢4 [6] then Eq. (<ref>) has no solution.
  If n ≡ 4 [6] then any solution of Eq. (<ref>) is a
  rotation of the solution (1,1,0,1,1,0, …, 1,1,0,1).


  Let x be any solution of Eq. (<ref>). By
  Lemma <ref> x_i≤ 1 for i = 0,…, n-1. Denote by
  n_0 the number of variables with x_i=0. Thus ∑_i=0^n-1
  x_i = n - n_0. Note that if x_i=0 then either x_i+1=1 or
  x_i-1=1, thus no adjacent variables have both value 0. Denote
  by l_1,…, l_n_0 the lengths of maximal sequences of
  consecutive x_i with x_i=1. Note that l_j ≥ 2 for all j.
  Then 
    ∑_i=0^n-1 x_i = ∑_j=1^n_0 l_j = 2n_0 +
      ∑_j=1^n_0 (l_j-2).
 This implies 
    3 ∑_i=0^n-1 x_i =
      2n + ∑_j=1^n_0 (l_j-2).
 If n ≡ 0 [3] then
  ∑_i=0^n-1 x_i ≥ 2n/3 = f(n). A contradiction. If n
  ≡ 2 [3] then again this leads to the contradiction
  ∑_i=0^n-1 x_i = 2⌊ n/3 ⌋ + (4 + ∑_j=1^n_0
  (l_j-2))/3 ≥ 2⌊ n/3 ⌋ + 2 ≥ f(n). Finally if n
  ≡ 1 [6] then ∑_i=0^n-1 x_i = 2⌊ n/3 ⌋ +
  (2 + ∑_j=1^n_0 (l_j-2))/3≥ 2⌊ n/3 ⌋ + 1 =f(n).
  This contradiction proves that for n ≢4 [6]
  Eq. (<ref>) has no solution.

  Let n ≡ 4 [6]. Then ∑_i=0^n-1 x_i = 2⌊ n/3
  ⌋ + (2 + ∑_j=1^n_0 (l_j-2))/3 <f(n) = 2⌊ n/3
  ⌋ + 1 implies 3 = 2 + ∑_j=1^n_0 (l_j-2). This yields
  that there exists i such that l_i=3 and l_j=2 for all
  j≠i. Thus, x is a rotation of the solution (1,1,0,1,1,0,
  …, 1,1,0,1).



  The solution x=(1,1,0,1,1,0, …, 1,1,0,1) is not induced by a
  -do­minating set of P(n,2).



  Assume there exists a -do­minating set S such that
  x_i=γ_S(b_i). Two vertices of the first two pairs must be in
  S. All four possibilities lead to a contradiction as shown in the
  following.

  
  
  
  
  
  
  
  

Case 1. v_0, u_1∈ S (see Fig. <ref>). Since S is
-do­minating the lower vertex of the last pair p_n-1 must be
in S. Now the same argument implies that the middle vertex of pair
p_3 must be in S. This yields that the lower vertex of pair p_7
must be in S, otherwise the lower vertex of pair p_5 is not
dominated. Repeating this argument shows that the lower vertex of pair
p_n-3 must be in S (note that n ≡ 4 [6]). Thus, S does
not dominate the middle vertex of pair p_n-2. Contradiction.



Case 2. u_0, v_1∈ S (see Fig. <ref>).
In order to dominate the middle vertex of pair p_2 the middle vertex
of p_3 must be in S. Similarly the lower vertex of pair p_7
must be in S to dominate the lower vertex of p_5. This results in
the pattern shown in Fig. <ref>. This is impossible because
all three neighbors of the lower vertex of p_n-1 are in S.



Case 3. u_0, u_1 ∈ S. The same reasoning as above leads
to the situation depicted in Fig. <ref>. This gives also
rise to a contradiction since the upper vertex of pair p_n-2 is
not dominated.



Case 4. v_0, v_1∈ S. The same reasoning as above leads
to the situation depicted in Fig. <ref>. This is impossible
because all three neighbors of the lower vertex of p_n-1 are in
S.




This concludes the proof of Theorem <ref> for the case B_1(S)
= ∅.










 §.§ Case B_1(S) ≠∅



The following simple observation is based on the fact that the central
vertex of a block b can only be dominated by a vertex within b.


  Any positive block b∈ B_1(S) corresponds to one of the
  four blocks shown in Fig. <ref>. A similar result holds
  for negative blocks.





In the following the four different types of blocks are considered
individually. 

  
Let S be a -dominating set of P (n,
  2) containing a block b of type B and n ≥ 12. Then there
  exists a -dominating set S' of P (n, 2) not containing a
  block of type B such that | S' | = | S |.










  In order to dominate v_i-1 and v_i+1 from block b,
  vertices v_i-3 from block b^- and v_i+3 from b^+ need to be
  in S. The idea is to move some
  dominating nodes such that block b is not no longer of type B and
  no new block of type B emerges while S is still -dominating
  and the cardinality of S remains. The proof is divided into four
  cases, considering whether u_i-2 from block b^- and
  u_i+2 from b^+ are in S or not. The notation of the nodes is taken from Fig. <ref>.

  Case 1. u_i-2, u_i+2∈ S. If v_i-4 and
  v_i+4 are not in S then S'= S / { u_i}∪{ v_i}. If
  v_i-4 or v_i+4 are in S then S'= S / { u_i-2}∪{ u_i-1} or S'= S / { u_i+2}∪{ u_i+1}.

  Case 2. u_i-2∉S, u_i+2∈ S. To dominate
  u_i-2 and v_i-2 we consider two subcases.

  Subcase 2.1. v_i-2∈ S. If u_i-3 is not in S then
  S'= S / { u_i}∪{ u_i-1}. If u_i-3∈ S then there
  are three possibilities depending on which vertex dominates
  u_i+4. Hence, if u_i+3∈ S then S'= S / { u_i+2}∪{ v_i}. If v_i+4∈ S then S'= S / { u_i+2}∪{ u_i+1}. Otherwise, the vertex u_i+4 is dominated by
  node u_i+5 of block b^++ then S'= S / { u_i}∪{
  v_i-1}.

  Subcase 2.2. v_i-2∉S. This implies that u_i-3
  and v_i-4 from are both in S. Then S'= S / { u_i-3}∪{ u_i-1}.

  Case 3. u_i+2∉S,
  u_i-2∈ S. This case is symmetric to case 2.

  Case.4. u_i+2,u_i-2∉S. In order to dominate
  u_i-2 and v_i-2 two situations must be considered.
 
  Subcase 4.1. v_i-2∈ S. Since v_i-2 is in S and
  v_i is not in S then v_i+2 cannot be a dominating node. This
  yields that u_i+3 and v_i+4 are in S. Then S'= S / {
  u_i+3}∪{ u_i+1}.

  Subcase 4.2. v_i-2∉S. This implies u_i-3,
  v_i-4∈ S. Therefore, S'= S / { u_i-3}∪{ u_i-1}.
 

The next Lemma finally completes the proof of Theorem <ref>.
 

  If B_1(S) ≠∅ and n ≥ 6 then |S|≥
  f(n).


  Let n be minimal such that the lemma is false. Then n ≥ 12
  by Lemma <ref>. Let S_B the set of all
  -dominating sets S of P(n,2) not containing a block of
  type B and |S|< f(n). Then B_1(S)≠∅ for all
  S∈ S_B by the first part of the proof. Let p be the
  largest number such that | B_1(S)|≥ p for each S∈ S_B. Then p≥ 1. Let  be the set of all S∈ S_B with | B_1(S)|=p.

  
  
  
  
  
  
  
  
  
  
  

  

  Claim 1: P(n,2) does not contain a
  block of type A for any S∈.

  Assume false. Let S∈ and b a positive block of type A. Then
  the nodes v_i+3 and u_i+2 of b^+ must be dominating.
  Assume γ_b^+(S)≥ 3. Then S'=S∖{u_i+2}∪{u_i} is also a [1,2]-dominating set. 
  Thus, γ_b(S')= 2. Then |
    B_1(S')| = | B_1(S)| -1 < p since γ_b(S)= 1. This
  yields S' ∉ S_B and therefore B_1(S) =
  ∅. Thus, γ_b^+(S)=2.

  

  Let b^++ be the positive block to the right of b^+. Then the
  nodes u_i+5 and v_i+6 of b^++ must be dominating. 
  Next we remove the nodes of the blocks
  b and b^+ and connect the corresponding nodes of blocks b^-
  and b^++. The resulting graph is isomorphic to P(n-6,2).
  Furthermore, S'=S∖{v_i, u_i+2, v_i+3, u_i+5} is a
  [1,2]-dominating set of this graph. 
  Thus, |S'|=|S|-4 ≥ f(n-6) by the choice
  of n. Therefore |S| ≥ f(n-6) + 4 = f(n). This implies |S|≥
  f(n). This contradiction proves claim 1 for positive blocks of
  type A. The same argument shows that there are no negative blocks
  of type A.

  Claim 2: P(n,2) does not contain a block of type
  D for any S∈

  Assume false. As above we only need to consider the positive case.
  Let S∈ and b a positive block of type D. Then nodes
  v_i+3 and u_i+2 of b^+ must be dominating. Assume
  γ_b^+(S)=2. Then again the nodes
  u_i+5 and v_i+6 of block b^++ must be dominating. We
  distinguish two cases. If v_i-2 is not a dominating node then
  S'=S∖{v_i+3}∪{v_i+1}
  else (v_i-2 is a dominating node) then we have again two subcases depending on γ_b^++(S).
  If γ_b^++(S)=2 then the nodes u_i+8 and v_i+9 of
  the block to the right of b^++ must be dominating nodes. We
  remove the nodes of the blocks b and b^+ and connect the
  corresponding nodes of blocks b^- and b^++ with
  S'=S∖{u_i-1, u_i+2, v_i+3, v_i+6}. Similar to
  the proof of claim 1 this leads to a contradiction. If
  γ_c(S)≥ 3 then at least one of the nodes v_i+5 and
  u_i+6 is a dominating node. Then we again remove the nodes of
  the blocks b and b^+ and connect the corresponding nodes of
  blocks b^- and b^++ with S'=S∖{u_i-1, u_i+2,
  v_i+3, u_i+5}. Similar to the proof of claim 1 this leads to a
  contradiction.

  Hence, γ_b^+(S)≥ 3. In the following we will construct a
  new [1,2]-dominating set S' with | B_1(S')|< p. This is
  a contradiction.
  
  Case 1. v_i+2,u_i+3∈ S. There are three subcases. If
  v_i-3∉S then S'=S∖{u_i+2}∪{v_i+1}
  and if v_i-2∉S then S'=S∖{u_i+2}∪{u_i}. If v_i-3,v_i-2∈ S
  then S'=S∖{u_i-1, u_i+2}∪{u_i, v_i}.

  Case 2. Neither v_i+2 nor u_i+3 are in S. Since
  γ_b^+(S)≥ 3 this implies that v_i+4 is a dominating
  node and S'=S∖{u_i+2}∪{u_i+1}.
  
  Case 3. If v_i+2∈ S and u_i+3∉S
  then S'=S∖{u_i+2}∪{u_i+1}.
  
  Case 4. If v_i+2∉S and u_i+3∈ S we distinguish two
  cases: If v_i+4∈ S then S'=S∖{u_i+2}∪{u_i+1} else we have four subcases depending on which node
  dominates u_i+5:
  
  
  * If v_i+5∈ S then
    S'=S∖{v_i+3}∪{u_i+1}.
  
  * If u_i+5∈ S then
    S'=S∖{u_i+3}∪{u_i+1}.
  
  * If u_i+6∈ S then we distinguish three cases depending on
    which node dominates v_i+4. If u_i+4∈ S then
    S'=S∖{u_i+2, u_i+4}∪{v_i+2, u_i}. If
    v_i+4∈ S then S'=S∖{u_i+2, v_i+4}∪{v_i+2, u_i}. Finally if v_i+6∈ S then we
    remove the nodes of the blocks b and b^+ and connect the
    corresponding nodes of blocks b^- and c.
  
  * If u_i+4∈ S then S'=S∖{u_i+2,u_i+3}∪{u_i+1, v_i+4}.
  
  This proves claim 2.
  



















  Claim 3: P(n,2) does not contain a
  block of type C for any S∈

  This case is symmetric to the second claim.

  Claim 4: P(n,2) does not contain a
  block of type B for any S∈

  If S contains a block of type B then by Lemma <ref> there
  exists S'∈ S_B which does not contain a block of type B.
  The above claims yield B_1(S')=∅. This
  contradiction concludes the proof of the lemma.





§ DETERMINATION OF (P(N,2))

In this section, we analyze the [1,2]-total dominating sets of
P(n,2) and prove the Theorem <ref>. For the case n=5 we
refer to Fig. <ref>. We split the proof into two lemmata.
Denote by g(n) the value of the right side of the equation in
Theorem <ref>.


  (P(n,2)) ≤ g(n) for n>5.



  In Fig. <ref>, we give the construction of the minimum
  [1,2]-total dominating set in P(n,2) for n ≡ 1[6]. The
  proposed construction is based on the selection of one pair of nodes
  of the middle in each block which corresponds to 2n/3 nodes. Then,
  we add two additional dominating nodes as depicted in color red in
  Fig. <ref>. For all other cases we refer to
  Fig. <ref> since the provided sets are already total
  dominating sets.



  (P(n,2)) ≥ g(n) for n>5.


  For n ≢1[6] this follows from Theorem <ref>. It
  remains to consider the case n ≡ 1[6]. Let S be a total
  -dominating set of minimum size of P(2,n) with |S| < g(n).
  Let G[S] be subgraph induced by S. By definition of a
  [1,2]-total dominating set, each connected component of G[S] has
  at least two vertices and every vertex of G[S] has degree 1 or
  2. Hence, every connected component is either a path or a cycle.
  Let x_l and y_l be the numbers of connected components that are
  paths and cycles of order l, respectively. Observe that x_1 = 0
  and y_1 = … = y_4 = 0. Moreover, each path of order l
  dominates at most 2l+2 vertices and each cycle of l vertices
  dominates at most 2l vertices. Thus,

    ∑_l≥ 2 (2l+2)x_l + 2ly_l ≥ 2n


    ∑_l≥ 2 l(x_l + y_l) = |S|

From (<ref>) and (<ref>) we can deduce

    |S| + ∑_l≥ 2 x_l ≥ n

Also observe that

    ∑_l≥ 2 lx_l ≥ 2 ∑_l≥ 2 x_l


Let n = 6k+1. Then g(n) = 4k+2 and |S| < 4k+2. Inequality
(<ref>) becomes |S| + ∑_l≥ 2 x_l ≥ 6k+1, thus
∑_l≥ 2 x_l ≥ 2k. From (<ref>) and using
(<ref>), we obtain 4k ≤∑_l≥ 2 lx_l + ∑_l≥
  2 ly_l ≤ 4k+1. This implies ∑_l≥ 2 ly_l = 0, thus 4k
≤ |S| = ∑_l≥ 2 lx_l ≤ 4k+1. Since ∑_l≥ 2 lx_l ≤
4k+1 and ∑_l≥ 2 x_l ≥ 2k, we have ∑_l≥ 2 lx_l ≤
2∑_l≥ 2 x_l+1. This is only possible if x_3 = 1 and x_j =
0 for all j >3. Thus, G[S] is the union one path P_3 and x_2
paths P_2. Since every P_2-component can dominate at most 6
vertices and the P_3-component can dominate at most 8 vertices, we
deduce 6x_2 + 8 ≥ 12k+2 =2n. On the other hand, recall |S| = 2x_2
+ 3 ≤ 4k+1 thus 6x_2 + 8 ≤ 12k+2. Hence, 6x_2 + 8 = 12k+2.
This implies that P(n,2) can be partitioned into x_2 components as
shown in Fig. <ref>(a) and one component shown in
Fig. <ref>(b). Suppose such a partitioning exists. In
the following we study the partitioning by making consecutive
extractions of components. Extracting a component means deleting all
its vertices from the graph. Moreover, an extraction is said to be
forced if there is no other option. Recall that the set of
vertices of P(n,2) is the union of the two sets U = {u_0,…,
u_n-1} and V = {v_0,…, v_n-1}. Vertices of U and V
form the two main cycles of P(n,2) respectively. Either all three
vertices of the P_3-component are on the same main cycle or two of
them are on one cycle and the third on the other. In the first case,
once the P_3 dominated component is extracted, the next forced
extraction of a P_2 dominated component would imply the appearance
of a vertex with a degree 2 (see Fig. <ref>(a)). In the
second case, after extracting the P_3 dominated component and after
several forced extractions of P_2 dominated components (see
Fig. <ref>(b)), it becomes obvious that such a partitioning
is impossible. Hence x_3 = 0, a contradiction.































§ CONCLUSION



Generalized Petersen graphs are very important structures in computer science and communication techniques since 
their particular structures and interesting properties.
In this paper, we considered a variant of the dominating set problem, called the [1,2]-dominating set problem.
We studied this problem in generalized Petersen graphs P(n,k) for k=2. 
We gave the exact values of the [1,2]-domination numbers
and the [1,2]-total domination numbers of P(n,2).
Obviously (P(n,1)) = γ(P(n,1)) and so as future work we suggest to study 
the [1,2]-domination numbers of P(n,k) with k ≥ 3.






plain


