TY - JOUR
ID - 14518
TI - On the rna number of generalized Petersen graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Sehrawat, Deepak
AU - Bhattacharjya, Bikash
AD - Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati, India
Y1 - 2024
PY - 2024
VL - 9
IS - 3
SP - 451
EP - 466
KW - generalized Petersen graph
KW - parity labeling
KW - parity signed graph
KW - rna number
KW - edge-cut
DO - 10.22049/cco.2023.27973.1408
N2 - 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.
UR - http://comb-opt.azaruniv.ac.ir/article_14518.html
L1 - http://comb-opt.azaruniv.ac.ir/article_14518_8fdf483020c02cbc615f57ea5434589e.pdf
ER -