  Determining the size of a maximum independent set of a graph $G$, denoted by
$\alpha(G)$, is an NP-hard problem. Therefore, many attempts are made to find
upper and lower bounds, or exact values of $\alpha (G)$ 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
$\alpha(P(n,k))$. With a computer program we have obtained exact values for
each $n<78$. In \cite{MR2381433} it is conjectured that $\beta(P(n, k)) \leq n
+ \lceil\frac{n}{5}\rceil $, for all $n$ and $k$. We prove this conjecture for
some cases. In particular, we show that if $ n> 3k$, the conjecture is valid.
We checked the conjecture with our table for $n < 78$ and it had no
inconsistency. Finally, we show that for every fix $k$, $\alpha(P(n, k))$ can
be computed using an algorithm with running time O(n).
