The decycling number of generalized Petersen graphs

A subset F⊂V(G)F⊂V(G) is called a decycling set   if the subgraph G−FG−F is acyclic. The minimum cardinality of a decycling set is called the decycling number   of GG, which is proposed first by Beineke and Vandell (1997). We use ∇(Pn,k)∇(Pn,k) to denote the decycling number of the generalized Petersen graphs Pn,kPn,k. This paper proves that ∇(Pn,k)={⌈n+12⌉,ifn≠2k,⌈k+12⌉,ifn=2k.