On the rna number of powers of cycles

Abstract

A signed graph $(G,\ddot{I}ƒ)$ on $n$ vertices is called a \textit{parity signed graph} if there is a bijective mapping $f:V(G)\to \{1,\dots ,n\}$ such that $f(u)$ and $f(v)$ have same parity if $\ddot{I}ƒ(uv)=1$, and opposite parities if $\ddot{I}ƒ(uv)=-1$ for each edge $uv$ in $G$. The \emph{rna} number $\ddot{I}{ƒ}^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. In other words, $\ddot{I}{ƒ}^{-}(G)$ is the smallest size of an edge-cut of $G$ such that the sizes of two sides differ at most one. Let $C_n^d$ be the $d\text{th}$ power of a cycle of order $n$. Recently, Acharya, Kureethara and Zaslavsky proved that the \emph{rna} number of a cycle $C_n$ on $n$ vertices is $2$. In this paper, we show for $2\le d<\lfloor \frac{n}{2}\rfloor$ that $2d\le \ddot{I}{ƒ}^{-}(C_n^d)\le d(d+1)$. Moreover, we prove that the graphs $C_n^2$ and $C_n^3$ achieve the upper bound of $d(d+1)$.

10 pages