Parity Labeling in Signed Graphs

Abstract

Let $S=(G,\sigma )$ be a signed graph where $G=(V,E)$ is a graph called the underlying graph of $S$ and $\sigma :E(G)\to \{+,-\}$. Let $f:V(G)\to \{1,2,\dots ,|V(G)|\}$ such that $\sigma (uv)=+$ if and only if $f(u)$ and $f(v)$ are of same parity and $\sigma (uv)=-$ if and only if $f(u)$ and $f(v)$ are of opposite parity. Under $f$ we get a signed graph $G_f$ denoted as $S$, which is a parity signed graph. In this paper, we initiate the study of parity labeling in signed graphs and we define and find `rna' number denoted as ${\sigma }^{-}(S)$ for some classes of signed graphs. We also characterize some signed graphs which are parity signed graphs. Some directions for further research are also suggested.

10 pages, 1 figure