RNA Number of Some Parity Signed Generalized Petersen Graphs

Abstract

A signed graph $\Sigma =(G,\sigma )$ is said to be parity signed if there exists a bijection $f:V(G)\to \{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\le {\sigma }^{-}(P(n,k))\le 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.