document: in a graph @xmath14 , an independent set @xmath15 is a subset of the vertices of @xmath0 such that no two vertices in @xmath15 are adjacent . 
   the independence number @xmath2 is the cardinality of a largest set of independent vertices and an independent set of size @xmath2 is called an @xmath16-set . 
   the maximum independent set problem is to find an independent set with the largest number of vertices in a given graph . 
   it is well - known that this problem is np - hard @xcite . 
   therefore , many attempts are made to find upper and lower bounds , or exact values of @xmath2 for special classes of graphs . 
   this paper is aimed toward studying this problem for the generalized petersen graphs .    for each @xmath7 and @xmath8  @xmath17 , a generalized petersen graph @xmath18 , is defined by vertex set @xmath19 and edge set @xmath20 ; where @xmath21 and subscripts are reduced modulo @xmath7 . 
   an induced subgraph on @xmath22-vertices is called the inner subgraph , and an induced subgraph on @xmath23-vertices is called the outer cycle . 
   + in addition , we call two vertices @xmath24 and @xmath25 as twin of each other and the edge between them as a spoke .    in @xcite , coxeter introduced this class of graphs . 
   later watkins @xcite called these graphs `` generalized petersen graphs '' , @xmath18 , and conjectured that they admit a tait coloring , except @xmath26 . 
   this conjecture later was proved in @xcite . since 
   1969 this class of graphs has been studied widely . 
   recently vertex domination and minimum vertex cover of @xmath18 have been studied . for more details 
   see for instance @xcite , @xcite , @xcite and @xcite .    a set @xmath27 of vertices of a graph @xmath28 
   is called a vertex cover of @xmath0 if every edge of @xmath0 has at least one endpoint in @xmath27 . 
   a vertex cover of a graph @xmath0 with the minimum possible cardinality is called a minimum vertex cover of @xmath0 and its size is denoted by @xmath29 . in @xcite and @xcite @xmath30 , has been studied . since for every simple graph @xmath0 , @xmath31 @xcite 
   , their results imply the following results for @xmath3 , and @xmath9 :    * @xmath32 * for all @xmath33 , @xmath34 . 
   * for all @xmath35 , @xmath36 * if both @xmath7 and @xmath8 are odd , then @xmath37 . + also , if @xmath38 , then @xmath39 . * @xmath40 @xmath41 if and only if @xmath7 is even and @xmath8 is odd . 
   * for all even @xmath8 , we have * * if @xmath42 then @xmath43 . * * if @xmath44 then @xmath45 . * for all odd @xmath7 , we have @xmath46 , where @xmath47 . 
   recently , fox et al . 
   proved the following results in @xcite :    * for all @xmath48 , @xmath49 * for any integer @xmath50 , we have that @xmath51 * if @xmath52 are integers with @xmath7 odd and @xmath8 even , then @xmath40 @xmath53 , where @xmath47 . * if @xmath52 are even , then @xmath40 @xmath54 , where @xmath47 . 
   notice that the problem of finding the size of a maximum independent set in the graph @xmath18 is trivial for even @xmath7 and odd @xmath8 , since @xmath18 is a bipartite graph . for odd @xmath7 and @xmath8 , 
   @xmath18 is not bipartite but we can remove a set of @xmath55 edges from @xmath18 to obtain a bipartite graph . 
   thus in this case we have @xmath56 . 
   so , for odd @xmath8 , we have upper and lower bounds for @xmath40 that are at most @xmath55 away from @xmath7 . 
   in contrast , for even @xmath8 , @xmath18 has a lot of odd cycles . 
   in fact , the number of odd cycles in @xmath18 is at least as large as @xmath13 . 
   this observation shows that for even @xmath8 , the graph @xmath18 is far from being a bipartite graph and as we see in continuation , we need more complicated arguments for finding lower and upper bounds for @xmath40 compared to the case that @xmath8 is an odd number . this paper is organized as follows . in section @xmath57 , we provide an upper bound for @xmath40 for even @xmath58 . in section @xmath59 , we present some lower bounds when @xmath8 is even . in both section @xmath57 and section @xmath59 we compare our bounds with the previously existing bounds . some exact values for @xmath40 
   are given in section @xmath60 by applying results presented in sections @xmath57 and section @xmath59 . 
   finally , in section @xmath61 we prove behsaz - hatami - mahmoodian s conjecture for some cases by using known lower bounds . 
   we checked the conjecture with our table for @xmath11 , and it had no inconsistency . 
   in this section we present an upper bound for @xmath40 when @xmath62 is even and we will show that the presented upper bound is equal to @xmath40 in some cases . our upper bound is better than the upper bound given by behsaz et.al . in @xcite . 
   + for @xmath63 , we call the set @xmath64 a @xmath65-segment and we denote it by @xmath66 . let @xmath67 $ ] be the subgraph of @xmath18 induced by @xmath66 .    let @xmath68 be the set of all maximum independent sets of @xmath18 . for every @xmath69 we denote by @xmath70 the number of @xmath65-segments @xmath66 for which @xmath71 . + define @xmath72 . since @xmath68 is nonempty , @xmath73 is also nonempty . 
   let @xmath74    [ note ] for any @xmath75 , @xmath76 if and only if @xmath77 .    [ type ] for any @xmath69 , we say @xmath66 is of   type @xmath78 with respect to @xmath79 if @xmath80 , of  type @xmath57 with respect to @xmath79 if @xmath81 , and of   type @xmath59 with respect to @xmath79 if @xmath82 . 
   + let @xmath83 . 
   for a given @xmath84 , we say @xmath66 is of special type @xmath57 with respect to @xmath79 , if @xmath85 and @xmath86 becomes an independent set for @xmath67 $ ] . 
   since @xmath67 $ ] has a perfect matching of spokes @xmath87 , @xmath88 . so every @xmath66 is one of the above types . 
   + note that @xmath89 . 
   [ lemma type 1 ] if @xmath8 is an even number then @xmath90 ) = 2k$ ] and @xmath67 $ ] has a unique @xmath16-set shown in figure [ type 1 ] . 
   +     as a type @xmath78 segment.,scaledwidth=80.0% ]     @xmath67 $ ] has a perfect matching @xmath91 . 
   so @xmath90 ) \leq 
   \frac{|v(g[i_t])|}{2 } = 2k.$ ] on the other hand , figure [ type 1 ] is an example of an independent set of @xmath67 $ ] of size @xmath65 . 
   so @xmath90)= 2k$ ] . 
   + to show that @xmath67 $ ] has a unique @xmath16-set , let @xmath79 be an @xmath16-set of @xmath92)$ ] . since @xmath90)= 2k$ ] , @xmath93 and @xmath79 must contain precisely one vertex from each edge @xmath94 where @xmath95 . 
   notice that the set of @xmath23-vertices of @xmath92)$ ] induces a path of length @xmath65 . 
   therefore @xmath96 the set of @xmath22-vertices of @xmath92)$ ] induces a matching of size @xmath8 . 
   this means that @xmath97 these two observations show that any @xmath16-set @xmath79 of @xmath67 $ ] has @xmath8 vertices from @xmath23-vertices and @xmath8 other vertices from @xmath22-vertices of @xmath98).$ ] moreover , every such @xmath79 contains precisely one vertex from each edge @xmath99 where @xmath100 and @xmath101 where @xmath102 . 
   now , consider two cases : + case 1 : @xmath103 . 
   + in this case , @xmath104 and @xmath105 are forced not to be in @xmath79 . 
   so @xmath106 is forced to be in @xmath79 . 
   then @xmath107 and @xmath108 are forced not to be in @xmath79 and this forces @xmath109 and @xmath110 to be in @xmath79 . since @xmath110 is in @xmath79 , @xmath111 . 
   therefore @xmath112 , so @xmath113 and thus @xmath114 so , we showed that if @xmath103 then @xmath115 too . 
   now , if we repeat the same argument for @xmath116 instead of @xmath117 , we can deduce that @xmath118 and by a simple induction , it follows that @xmath119 for any @xmath120 . 
   particularly , @xmath121 therefore @xmath122 this shows that @xmath123 . 
   hence @xmath124 and @xmath125 . 
   so @xmath126 but we already showed that @xmath109 is forced to be in @xmath79 . 
   this contradiction shows that there is no type @xmath78 @xmath66 for which @xmath127 + case 2 : @xmath128 . 
   + in this case , similar to the argument in case 1 , each vertex is either forced to be in @xmath79 or it is forced not to be in @xmath79 . 
   so , there is a unique pattern for @xmath129 when @xmath130 . 
   since the pattern shown in figure [ type 1 ] is an instance of an independent set of size @xmath65 for @xmath67 $ ] , it is the unique pattern for such an independent set . 
   lemma [ lemma type 1 ] guarantees that there is a unique pattern for @xmath131 , if @xmath66 is of special type @xmath57 with respect to @xmath79 . 
   [ lemma uv ] for every @xmath69 , if @xmath132 then @xmath133 , and @xmath134 also , if @xmath135 is a special type @xmath57 segment with respect to @xmath79 then @xmath136 and @xmath137 . 
   if @xmath132 then @xmath80 . so by lemma [ lemma type 1 ] , there is a unique pattern for @xmath131 . based on this pattern , @xmath138 and @xmath139 . 
   therefore @xmath136 and @xmath137 , since @xmath79 is an independent set of vertices of @xmath18 . 
   a similar argument shows that @xmath140 and @xmath141 . 
   the proof of the second part of the lemma is similar .    [ 
   corollary 1 ] if @xmath132 then @xmath142     notice that if @xmath143 then for any edge @xmath144)$ ] either @xmath145 or @xmath146 . since @xmath132 , lemma [ lemma uv ] implies that @xmath136 and @xmath147 . 
   on the other hand , @xmath148)$ ] for @xmath149 . 
   thus @xmath150    [ maintheorem ] @xmath151 for any even number @xmath62 and any integer @xmath152 . 
   let @xmath153 . 
   we consider two cases . 
   + case @xmath78 : @xmath154 . 
   + in this case @xmath155 . 
   so @xmath156 for any @xmath157 . 
   if we add all of these @xmath7 inequalities we get : + @xmath158 on the other hand @xmath159 , since every element of @xmath160 is contained in precisely @xmath65 of the sets @xmath66 . thus : @xmath161 case @xmath57 : @xmath162 + in this case @xmath163 . similar to the inequality [ e : 
   1 ] we have : + @xmath164 so , to prove the theorem , it suffices to show that there exists @xmath165 such that @xmath166 . 
   + if we can show that for any @xmath167 , there exists an @xmath168 so that @xmath169 , then it follows that @xmath166 . 
   + on the contrary , suppose that there exists @xmath170 in such a way that in the sequence @xmath171 before we see an element of @xmath172 , we see an element of @xmath173 . without loss of generality 
   we can assume that @xmath174 by lemma [ lemma type 1 ] , @xmath175 is of the form depicted in figure [ type 11 ] . 
   +     as a type @xmath78 segment.,scaledwidth=80.0% ]    since @xmath176 , by corollary [ corollary 1 ] , @xmath177 based on our assumption , @xmath178 in particular , @xmath179 . since @xmath180 , by lemma [ lemma uv ] we have @xmath181 . on the other hand , 
   we know that @xmath160 must have one vertex from each edge @xmath182 where @xmath183 since @xmath184 , either @xmath185 or @xmath186 . 
   but notice that @xmath187 is adjacent to @xmath188 which is in @xmath160 , for @xmath189 . 
   thus , @xmath190 and @xmath185 must be in @xmath160 . 
   this means that @xmath191 . 
   now , define @xmath192 . 
   one can easily see that @xmath193 . 
   based on the choice of @xmath153 , @xmath194 . 
   therefore , there must be an index @xmath195 so that @xmath196 . 
   since @xmath160 and @xmath197 agree on every element except @xmath198 and @xmath199 , the only candidate for @xmath200 is @xmath201 . 
   so @xmath202 and @xmath203 . 
   moreover @xmath204 and @xmath205 . thus @xmath206 . by proposition 
   [ note ] , @xmath207 . 
   notice that if any of @xmath208 are of type @xmath209 with respect to @xmath197 , they are of type @xmath209 with respect to @xmath160 , as well . 
   so , in the sequence @xmath208 , any type @xmath59 segment with respect to @xmath197 appears after an element of type @xmath78 with respect to @xmath197 . 
   since @xmath202 by corollary [ corollary 1 ] , @xmath210 . then from our assumption @xmath211 . 
   + this means that the same argument can be applied to @xmath197 and if we define @xmath212 , then @xmath213 . if we consecutively repeat this argument for @xmath214 where @xmath215 and @xmath216 , then we observe that @xmath217 and @xmath218 for @xmath219 , and none of @xmath220 are of type  @xmath78 with respect to @xmath160 . also , @xmath221 for @xmath222 are of special type  @xmath57 with respect to @xmath223 . 
   since @xmath223 and @xmath160 agree on the @xmath224 , then @xmath221 for @xmath222 are of special type  @xmath57 with respect to @xmath160 . + in other words , 
   if @xmath225 belongs to @xmath226 and the next element of @xmath226 appears before the first element of @xmath227 in the sequence @xmath228 then all of @xmath229 are special type @xmath57 with respect to @xmath160 . 
   in particular , @xmath230 is of special type @xmath57 with respect to @xmath160 . + as @xmath231 , by lemma [ lemma uv ] , @xmath232 and since @xmath233 and @xmath160 agree on the @xmath234 we conclude that @xmath235 . + now consider three cases :    * @xmath236 : + since @xmath230 is of special type @xmath57 with respect to @xmath160 , by lemma [ lemma uv ] , we have @xmath237 . 
   this is a contradiction as we assumed @xmath180 and therefore @xmath238 . 
   * @xmath239 : + since @xmath180 , by lemma [ lemma uv ] , @xmath240 . 
   also we know that @xmath241 . 
   thus , @xmath242 is of type @xmath59 with respect to @xmath160 and none of @xmath243 are of type @xmath78 with respect to @xmath160 which is a contradiction . 
   * @xmath244 : + @xmath225 is of type @xmath78 with respect to @xmath160 and for every @xmath245 , @xmath221 is of special type @xmath57 with respect to @xmath160 . in particular 
   , @xmath230 is of special type @xmath57 with respect to @xmath160 , and therefore @xmath246 , ( see figure  [ type 2 ] ) . on the other hand , @xmath247 as @xmath180 , and since @xmath248 , @xmath249 is adjacent to @xmath250 . 
   this is a contradiction . 
   so in all the cases , we get a contradiction which means , after any type @xmath78 segment @xmath251 , a type @xmath59 segment @xmath252 will appear before we see another type @xmath78 segment . 
   this means that @xmath253 and the theorem follows , as we argued earlier . 
   in this section we introduce some lower bounds for @xmath40 where @xmath8 is even and @xmath189 . 
   + here we explain a construction for an independent set in @xmath18 for even numbers @xmath7 and @xmath8 . 
   it happens that for every even @xmath254 , our lower bound is equal to the actual value , using a computer program for finding the independence number in @xmath18 . 
   [ nk even ] if @xmath7 and @xmath8 are even and @xmath62 then : @xmath255 where @xmath200 is the remainder of @xmath7 modulo @xmath65 . 
   we partition the vertices of @xmath18 into @xmath256 @xmath65-segments and one @xmath200-segment . 
   since @xmath7 and @xmath8 are even numbers , @xmath200 is also an even number and it is straightforward to see that if we choose a subset of the form shown in figure [ type 2 ] , from each @xmath65-segment they form an independent set @xmath160 of size @xmath257 . 
   then we try to extend this independent set by adding more vertices from the remaining @xmath200-segment . without loss of generality 
   , we may assume that the @xmath200-segment consists of the vertices @xmath258 . 
   consider two cases :    *   @xmath259 : + in this case the set @xmath260 is an independent set of size @xmath261 . *   @xmath262 : + in this case the set : + @xmath263 is an independent set of size @xmath264        as a special type @xmath57 segment.,scaledwidth=80.0% ]    in the next theorem we establish a lower bound for @xmath12 for odd @xmath7 and even @xmath8 . 
   +    [ n odd k even ] if @xmath7 is odd and @xmath62 is even then we have :    @xmath265    where @xmath200 is the remainder of @xmath7 modulo @xmath65 . 
   we construct an independent set for the graph @xmath18 . 
   similar to the proof of theorem [ nk even ] , first we partition the vertices of the graph into @xmath266 @xmath65-segments and a remaining segment of size @xmath200 . without loss of generality , we can assume that the last @xmath65-segment starts from the first spoke and the remaining segment starts from the @xmath267-st spoke and finishes at the @xmath268-th spoke . 
   we also label the @xmath65-segments with indices @xmath269 .    from each of @xmath65-segments 
   @xmath270 , we choose @xmath271 vertices as shown in figure [ type 2 ] . 
   we also choose the following vertices from the last @xmath65-segment and the remaining @xmath200-segment :    * @xmath272 : + @xmath273 * @xmath274 + @xmath275 * @xmath276 + @xmath277    one can easily check that in each case , the given set is an independent set of size specified in the theorem . 
   notice that the upper bound given in theorem [ maintheorem ] and the lower bound in theorem [ nk even ] , and theorem [ n odd k even ] are very close to each other for every fixed even @xmath189 . 
   more precisely , we have the following corollary :    if @xmath278 is an even number then @xmath279    notice that our lower bounds are considerably better than the lower bounds obtained in @xcite and @xcite . 
   in this section , we will find the exact value of @xmath40 for some pairs of @xmath52 . 
   +    [ k=4 ] if @xmath280 , then : + @xmath281 @xmath282    this result is straight consequence of theorems  [ maintheorem ] , [ nk even ] , and [ n odd k even ] . 
   notice that for @xmath283 and @xmath284 or @xmath285 , the upper bound and lower bound differ by @xmath78 . 
   in fact , for @xmath286 the exact of @xmath3 is the same as our lower bound as we checked by computer . 
   if @xmath278 is an even number and @xmath287 or @xmath288 then @xmath289 . 
   this assertion is trivial consequence of theorems [ maintheorem],[nk even ] and [ n odd k even ] . in fact 
   the upper bound and lower bounds we have for @xmath3 are identical in these cases . 
   [ conj 1 ] ( @xcite ) . for all @xmath7 , @xmath8 
   we have @xmath290 . 
   +    notice that , since @xmath291 , this conjecture is equivalent to @xmath292 . 
   the above conjecture is valid in the following cases :    * @xmath293 . 
   * @xmath7 is even and @xmath8 is odd . 
   * @xmath52 are odd and @xmath294 . 
   * @xmath52 are even . 
   * @xmath7 is odd , @xmath8 is even and @xmath295 . 
   * this case is a straight consequence of ( i ) , ( ii ) , ( iii ) , proposition [ k=4 ] and ( viii ) . * in this case @xmath18 is a bipartite graph and @xmath296 . 
   * @xmath297 ( @xcite ) . for @xmath298 
   this lower bound is greater than @xmath299 . 
   * let @xmath300 where @xmath301 and @xmath302 . 
   we consider the following subcases : * * if @xmath259 and @xmath303 then by theorem [ nk even ] , @xmath304 for any @xmath305 . for @xmath306 conjecture holds based on the information provided in table @xmath78 . * * if @xmath307 and @xmath308 then by theorem [ nk even ] , @xmath309 for any @xmath310 . for @xmath311 , conjecture follows from @xmath312 . * * if @xmath262 and @xmath303 then by theorem [ nk even ] , @xmath313 for any @xmath314 . for @xmath315 conjecture holds based on the information provided in table @xmath78 . 
   * * if @xmath316 and @xmath308 then by theorem [ nk even ] , @xmath317 for any @xmath318 . for @xmath319 , conjecture follows from @xmath312 . 
   * similar to the previous part , let @xmath300 where @xmath301 and @xmath302 . 
   we consider the following subcases : * * if @xmath320 and @xmath303 then @xmath321 which is isomorphic to @xmath322 . 
   ( for more information about isomorphic generalized petersen graphs see @xcite ) . * * if @xmath320 and @xmath323 then by theorem [ n odd k even ] , @xmath324 for every @xmath325 . * * if @xmath326 then @xmath327 has to be larger than @xmath78 . 
   in fact if @xmath326 and @xmath303 then @xmath328 . for @xmath326 and @xmath329 then by theorem [ n odd k even ] , @xmath330 for every @xmath331 . 
   ( note that since @xmath7 is odd and @xmath8 is even , @xmath332 implies that @xmath333 ) . * * if @xmath334 then by theorem [ n odd k even ] , @xmath335 for @xmath336 . for @xmath337 
   then the assertion is concluded from part @xmath312 .       if @xmath295 then @xmath338 , and behsaz - hatami - mahmoodian s conjecture holds . 
   in this section we will prove that the independence number of generalized petersen graphs with fixed @xmath8 can be found in linear time , @xmath13 . 
   this result is a special case of a deep theorem stating that the problem of finding the independence number of graphs with bounded treewidth can be solved in linear time of the number of vertices of the graph .    in the continuation 
   we will show that for every fixed @xmath8 and any integer @xmath9 the treewidth of @xmath18 is bounded . 
   first , we need to formally define the concepts of tree decomposition and treewidth of a graph . 
   let @xmath14 be a graph . 
   a tree decomposition of @xmath0 is a pair @xmath339 , where @xmath340 is a family of subsets of @xmath341 , and @xmath342 is a tree whose nodes are the subsets @xmath343 , satisfying the following properties :    * the union of all sets @xmath343 equals @xmath341 . 
   * for every edge @xmath344 in the graph , there is a subset @xmath343 that contains both @xmath22 and @xmath345 . * 
   if @xmath343 is on the path from @xmath346 to @xmath347 in @xmath342 then @xmath348 . in other words , for all vertices @xmath349 all nodes @xmath346 which contain @xmath22 induce a connected subtree of @xmath342 . 
   the width of @xmath350 is defined to be the size of the largest @xmath346 minus one . 
   the treewidth , @xmath351 , of the graph @xmath0 is defined to be the minimum width of all its tree decompositions . 
   the treewidth will be taken as a measure of how much a graph resembles a tree . 
   ( @xcite ) [ alghorithm ] the problem of finding a maximum independent set of a graph @xmath0 with bounded treewidth , @xmath352 can be solved in @xmath353 by dynamic programming techniques , where @xmath7 is the number of vertices of graph .    for more details 
   see for instance @xcite , @xcite , @xcite , and @xcite .    for any fixed @xmath8 , 
   the problem of finding independence number of the graphs @xmath18 can be solved by an algorithm with running time @xmath13 .     by theorem  [ alghorithm ] , we only need to show that for a given number @xmath8 , the treewidth of @xmath18 is bounded . 
   consider the following tree decomposition of @xmath18 of width @xmath354 . without loss of generality we can only consider the case where @xmath355 . 
   let @xmath342 be the path of order @xmath356 and define @xmath357 as follows : + @xmath358 + @xmath359 + @xmath360 + @xmath361 + @xmath362 and so on . 
   + notice that in each step we remove two elements and add two other elements . 
   therefore @xmath363 for all @xmath209 . 
   one can easily see that @xmath350 is a tree decomposition for @xmath18 where @xmath364 . 
   thus , @xmath365 and by theorem [ alghorithm ] , the proof is complete . 
   table @xmath78 : independence number of @xmath366 . 
   the authors would like to thank the referee for careful reading of this paper and very helpful comments . and 
   the authors like to thank professor e. s. mahmoodian for suggesting the problem and very useful comments . 
   we also thank nima aghdaei , and hadi moshaiedi for their computer program and algorithm to create presented table of @xmath3 . 
   hans  l. bodlaender . 
   dynamic programming on graphs with bounded treewidth . in _ 
   automata , languages and programming ( tampere , 1988 ) _ , volume 317 of _ lecture notes in comput . 
   _ , pages 105118 . 
   springer , berlin , 1988 .
summary: determining the size of a maximum independent set of a graph @xmath0 , denoted by @xmath1 , is an np - hard problem . 
   therefore many attempts are made to find upper and lower bounds , or exact values of @xmath2 for special classes of graphs . 
   this paper is aimed toward studying this problem for the class of generalized petersen graphs . 
   we find new upper and lower bounds and some exact values for @xmath3 . with a computer program we have obtained exact values for each @xmath4 . in @xcite 
   it is conjectured that the size of the minimum vertex cover , @xmath5 , is less than or equal to @xmath6 , for all @xmath7 and @xmath8 with @xmath9 . 
   we prove this conjecture for some cases . 
   in particular , we show that if @xmath10 , the conjecture is valid . 
   we checked the conjecture with our table for @xmath11 and it had no inconsistency . 
   finally , we show that for every fixed @xmath8 , @xmath12 can be computed using an algorithm with running time @xmath13 . 
   * keywords * : generalized petersen graphs , independent set , tree decomposition