%0 Journal Article
%T On the rna number of generalized Petersen graphs
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Sehrawat, Deepak
%A Bhattacharjya, Bikash
%D 2024
%\ 09/01/2024
%V 9
%N 3
%P 451-466
%! On the rna number of generalized Petersen graphs
%K generalized Petersen graph
%K parity labeling
%K parity signed graph
%K rna number
%K edge-cut
%R 10.22049/cco.2023.27973.1408
%X A signed graph $(G,\sigma)$ is called a parity signed graph if there exists a bijective mapping $f \colon V(G) \rightarrow \{1,\ldots,|V(G)|\}$ such that for each edge $uv$ in $G$, $f(u)$ and $f(v)$ have same parity if $\sigma(uv)=+1$, and opposite parity if $\sigma(uv)=-1$. The \emph{rna} number $\sigma^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. Equivalently, $\sigma^{-}(G)$ is the least size of an edge-cut of $G$ that has nearly equal sides.In this paper, we show that for the generalized Petersen graph $P_{n,k}$, $\sigma^{-}(P_{n,k})$ lies between $3$ and $n$. Moreover, we determine the exact value of $\sigma^{-}(P_{n,k})$ for $k\in \{1,2\}$. The \emph{rna} numbers of some famous generalized Petersen graphs, namely, Petersen graph, D\" urer graph, M\" obius-Kantor graph, Dodecahedron, Desargues graph and Nauru graph are also computed. Recently, Acharya, Kureethara and Zaslavsky characterized the structure of those graphs whose \emph{rna} number is $1$. We use this characterization to show that the smallest order of a $(4n+1)$-regular graph having \emph{rna} number $1$ is $8n+6$. We also prove the smallest order of $(4n-1)$-regular graphs having \emph{rna} number $1$ is bounded above by $12n-2$. In particular, we show that the smallest order of a cubic graph having \emph{rna} number $1$ is 10.
%U http://comb-opt.azaruniv.ac.ir/article_14518_8fdf483020c02cbc615f57ea5434589e.pdf