  A signed graph $\Sigma=(G,\sigma)$ is said to be parity signed if there
exists a bijection $f : V(G) \rightarrow \{1,2,...,|V(G)|\}$ such that
$\sigma(uv)=+$ if and only if $f(u)$ and $f(v)$ are of same parity, where $uv$
is an edge of $G$. The rna number of a graph $G$, denoted $\sigma^{-}(G)$, is
the minimum number of negative edges among all possible parity signed graphs
over $G$. The rna number is also equal to the minimum cut size that has nearly
equal sides.
  In this paper, for generalized Petersen graph $P(n,k)$, we prove that $3 \leq
\sigma^{-}(P(n,k)) \leq n$ and these bounds are sharp. The exact value of
$\sigma^{-}(P(n,k))$ is determined for $k=1,2$. Some famous generalized
Petersen graphs namely, Petersen graph $P(5,2)$, Durer graph $P(6,2)$,
Mobius-Kantor graph $P(8,3)$, Dodecahedron $P(10,2)$, Desargues graph $P(10,3)$
and Nauru graph $P(12,5)$ are also treated.
  We show that the minimum order of a $(4n-1)$-regular graph having rna number
one is bounded above by $12n-2$. The sharpness of this upper bound is also
shown for $n=1$. We also show that the minimum order of a $(4n+1)$-regular
graph having rna number one is $8n+6$. Finally, for any simple connected graph
of order $n$, we propose an $O(2^n + n^{\lfloor \frac{n}{2} \rfloor})$ time
algorithm for computing its rna number.
