  For natural numbers $n$ and $k$ ($n > 2k$), a generalized Petersen graph
$P(n,k)$, is defined by vertex set $\lbrace u_i,v_i\rbrace$ and edge set
$\lbrace u_iu_{i+1},u_iv_i,v_iv_{i+k}\rbrace$; where $i = 1,2,\dots,n$ and
subscripts are reduced modulo $n$. Here first, we characterize minimum vertex
covers in generalized Petersen graphs. Second, we present a lower bound and
some upper bounds for $\beta(P(n,k))$, the size of minimum vertex cover of
$P(n,k)$. Third, in some cases, we determine the exact values of
$\beta(P(n,k))$. Our conjecture is that $\beta(P(n,k)) \le n +
\lceil\frac{n}{5}\rceil$, for all $n$ and $k$.

Discrete Mathematics